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 : 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://www.numdam.org/articles/10.1051/ita:2007016/}
}
TY  - JOUR
AU  - Honkala, Juha
TI  - A periodicity property of iterated morphisms
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 215
EP  - 223
VL  - 41
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007016/
DO  - 10.1051/ita:2007016
LA  - en
ID  - ITA_2007__41_2_215_0
ER  - 
%0 Journal Article
%A Honkala, Juha
%T A periodicity property of iterated morphisms
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 215-223
%V 41
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007016/
%R 10.1051/ita:2007016
%G en
%F 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) no. 2, pp. 215-223. doi : 10.1051/ita:2007016. http://www.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

[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

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

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

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

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

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

Cité par Sources :