Suppose is a morphism and . For every nonnegative integer , let be the longest common prefix of and , and let be words such that and . We prove that there is a positive integer such that for any positive integer , the prefixes of (resp. ) of length form an ultimately periodic sequence having period . Further, there is a value of which works for all words .
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/} }
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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita:2007016/
[1] Elementary homomorphisms and a solution of the D0L sequence equivalence problem. Theoret. Comput. Sci. 7 (1978) 169-183. | Zbl
and ,[2] Subword complexities of various classes of deterministic developmental languages without interactions. Theoret. Comput. Sci. 1 (1975) 59-75. | Zbl
, and ,[3] Developmental Systems and Languages. North-Holland, Amsterdam (1975). | MR | Zbl
and ,[4] The equivalence problem for DF0L languages and power series. J. Comput. Syst. Sci. 65 (2002) 377-392. | Zbl
,[5] The Mathematical Theory of L Systems. Academic Press, New York (1980). | MR | Zbl
and ,[6] Handbook of Formal Languages. Vol. 1-3, Springer, Berlin (1997). | Zbl
and (Eds.),[7] Jewels of Formal Language Theory. Computer Science Press, Rockville, Md. (1981). | MR | Zbl
,Cité par Sources :