A periodicity property of iterated morphisms

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 ${𝑓}^{𝑛}\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^{*}$.

Détail

DOI : 10.1051/ita:2007016

Classification : 68Q45, 68R15
Keywords: iterated morphism, periodicity