A periodicity property of iterated morphisms
Honkala, Juha
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 215-223 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Suppose f:X * →X * is a morphism and u,v∈X * . 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,v∈X * .

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007016
Classification:  68Q45,  68R15 
@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},
     volume = {41},
     year = {2007},
     pages = {215-223},
     doi = {10.1051/ita:2007016},
     mrnumber = {2350645},
     zbl = {pre05235509},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_2_215_0}
}

Honkala, Juha. A periodicity property of iterated morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 215-223. doi : 10.1051/ita:2007016. http://gdmltest.u-ga.fr/item/ITA_2007__41_2_215_0/

[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