×

On the periodicity of morphisms on free monoids. (English) Zbl 0608.68065

It is shown that for a given endomorphism h on a given finitely generated free monoid there are only finitely many primitive words w for which \(h(w)=w^ n\) for some \(n\geq 2\). Moreover, all such words can be effectively found. Using this result, the D0L periodicity problem is shown to be decidable, that is, it is decidable whether there exist words v and w for a given u such that \(h^{\omega}(u)=vw^{\omega}\), where \(h^{\omega}(u)\) is the limit of the sequence \(u,h(u),h^ 2(u),... \). This latter result has also been solved by J. Pansiot [Decidability of periodicity for infinite words, RAIRO Inf. Théor. 20, 43-46 (1986)] using a different method.

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. K. CULIK II, The Ultimate Equivalence Problem for DOL Systems, Acta Informatica, Vol. 10, 1978, pp. 79-84. Zbl0385.68060 MR495230 · Zbl 0385.68060 · doi:10.1007/BF00260925
[2] 2. A. EHRENFEUCHT and G. ROZENBERG, On Simplifications of PDOL Systems, Proceedings of a Conference on Theoretical Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1977. Zbl0414.68046 MR495235 · Zbl 0414.68046
[3] 3. T. HARJU and M. LINNA, The equations h(w) = wn in binary alphabets, Theoret. Comput. Sci. 33, 1984, pp. 327-329. Zbl0548.20044 MR767397 · Zbl 0548.20044 · doi:10.1016/0304-3975(84)90093-8
[4] 4. T. HEAD, Adherence Equivalence is Decidable for DOL Languages, Proceedings of a Symposium of Theoretical Aspects of Computer Science, Paris, 1984, Springer Lecture Notes in Computer Science, Vol. 166, 1984, pp. 241-248. Zbl0543.68060 MR773326 · Zbl 0543.68060
[5] 5. M. LINNA, The Decidability of the DOL Prefix Problem, Int. J. Comput. Math., Vol. 6, 1977, pp. 127-142. Zbl0358.68114 MR471462 · Zbl 0358.68114 · doi:10.1080/00207167708803132
[6] 6. M. LINNA, On Periodic \omega -Sequences Obtained by Iterating Morphisms, Ann. Univ. Turkuensis, Ser. A I 186 1984, pp. 64-71. Zbl0547.68074 MR748519 · Zbl 0547.68074
[7] 7. A. SALOMAA, Comparative Decision Problems between Sequential and Parallel Rewriting, Proc. Symp. Uniformly Structured Automata and Logic, Tokyo, 1975, pp. 62-66. MR489059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.