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}^{*}\to {X}^{*}$ is a morphism and $u,v\in {X}^{*}$. For every nonnegative integer $n$, let ${z}_{n}$ be the longest common prefix of ${𝑓}^{𝑛}\left(𝑢\right)$ and ${𝑓}^{𝑛}\left(𝑣\right)$, and let ${u}_{n},{v}_{n}\in {X}^{*}$ be words such that ${𝑓}^{𝑛}\left(𝑢\right)={𝑧}_{𝑛}{𝑢}_{𝑛}$ and ${𝑓}^{𝑛}\left(𝑣\right)={𝑧}_{𝑛}{𝑣}_{𝑛}$. 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,v\in {X}^{*}$.

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