A periodicity property of iterated morphisms

Department of Mathematics, University of Turku, 20014 Turku, Finland; juha.honkala@utu.fi

Received: 30 August 2005
Accepted: 13 September 2006

Abstract

Suppose ƒ : X* → X* is a morphism and u,v ∈ X*. For every nonnegative integer n, let z_n be the longest common prefix of ƒⁿ(u) and ƒⁿ(v), and let u_n,v_n ∈ X* be words such that ƒⁿ(u) = zⁿuⁿ and ƒⁿ(v) = zⁿvⁿ. 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*.