Article ID Journal Published Year Pages File Type
430849 Journal of Discrete Algorithms 2015 9 Pages PDF
Abstract

We describe a simple algorithm that finds all primitive words v   such that vkvk is a factor of the language of a given D0L-system for all k. It follows that the number of such words is finite. This polynomial-time algorithm can be also used to decide whether a D0L-system is repetitive.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
An algorithm for enumerating all infinite repetitions in a D0L-system
Authors
, ,