Repetitiveness of languages generated by morphisms (Q1575438): Difference between revisions

We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive [\textit{A. Ehrenfeucht} and \textit{G. Rozenberg}, Inf. Control 59, 13-35 (1983; Zbl 0549.68076)]. From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of \textit{P. Séébold} [Bull. EATCS 36, 137-151 (1988; Zbl 0678.68072)] on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(\(f\)) generated by \(f\) or the language SL(\(f\)) of subwords of L(\(f\)) are context-free or even regular.