A periodicity property of iterated morphisms
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 2, pp. 215-223.

Suppose f:X * X * is a morphism and u,vX * . For every nonnegative integer n, let z n be the longest common prefix of 𝑓 𝑛 (𝑢) and 𝑓 𝑛 (𝑣), and let u n ,v n X * be words such that 𝑓 𝑛 (𝑢)=𝑧 𝑛 𝑢 𝑛 and 𝑓 𝑛 (𝑣)=𝑧 𝑛 𝑣 𝑛 . We prove that there is a positive integer q such that for any positive integer p, the prefixes of u n (resp. v n ) of length p form an ultimately periodic sequence having period q. Further, there is a value of q which works for all words u,vX * .

DOI : https://doi.org/10.1051/ita:2007016
Classification : 68Q45,  68R15
Mots clés : iterated morphism, periodicity
@article{ITA_2007__41_2_215_0,
     author = {Honkala, Juha},
     title = {A periodicity property of iterated morphisms},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {215--223},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {2},
     year = {2007},
     doi = {10.1051/ita:2007016},
     mrnumber = {2350645},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2007016/}
}
Honkala, Juha. A periodicity property of iterated morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 2, pp. 215-223. doi : 10.1051/ita:2007016. http://archive.numdam.org/articles/10.1051/ita:2007016/

[1] A. Ehrenfeucht and G. Rozenberg, Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | Zbl 0407.68085

[2] A. Ehrenfeucht, K.P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interactions. Theoret. Comput. Sci. 1 (1975) 59-75. | Zbl 0316.68043

[3] G.T. Herman and G. Rozenberg, Developmental Systems and Languages. North-Holland, Amsterdam (1975). | MR 495247 | Zbl 0306.68045

[4] J. Honkala, The equivalence problem for DF0L languages and power series. J. Comput. Syst. Sci. 65 (2002) 377-392. | Zbl 1059.68062

[5] G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York (1980). | MR 561711 | Zbl 0508.68031

[6] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages. Vol. 1-3, Springer, Berlin (1997). | Zbl 0866.68057

[7] A. Salomaa, Jewels of Formal Language Theory. Computer Science Press, Rockville, Md. (1981). | MR 618124 | Zbl 0487.68064