A periodicity property of iterated morphisms

Honkala, Juha

doi:10.1051/ita:2007016

Honkala, Juha

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 2, pp. 215-223.

Résumé

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 $𝑓^{𝑛} (𝑢)$ and $𝑓^{𝑛} (𝑣)$ , and let $u_{n}, v_{n} \in 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 \in X^{*}$ .

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/

Bibliographie
Cité par

[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 :