On periodic \(\omega\) -sequences obtained by iterating morphisms. (English) Zbl 0547.68074

One of the basic questions concerning the DOL systems is the periodicity of generated \(\omega\) -words. For instance, the proof of the decidability of the adherence equivalence problem for DOL languages by T. Head [Theor. Comput. Sci. 31, 139-149 (1984)] is essentially based on such considerations. In the present paper the DOL periodicity problem (Is it decidable whether a given DOL system generates ultimately periodic \(\omega\) -words?) is solved in the special case where the period is assumed to be known in advance. Recently, also the general case has been solved affirmatively by T. Harju and M. Linna [On the periodicity morphisms on free monoids, submitted for publication].


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems