A1 Refereed original research article in a scientific journal
A periodicity property of iterated morphisms
Authors: Honkala J
Publisher: EDP SCIENCES S A
Publication year: 2007
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Volume: 41
Issue: 2
First page : 215
Last page: 223
Number of pages: 9
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita200716
Abstract
Suppose f : X* ->. X* is a morphism and u, v epsilon X*. For every nonnegative integer n, let z(n) be the longest common prefix of f(n) (u) and f(n) (v), and let u(n), v(n) epsilon X* be words such that f(n) (u) = z(n) u(n) and f(n) (v) = z(n) v(n). 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 epsilon X*.
Suppose f : X* ->. X* is a morphism and u, v epsilon X*. For every nonnegative integer n, let z(n) be the longest common prefix of f(n) (u) and f(n) (v), and let u(n), v(n) epsilon X* be words such that f(n) (u) = z(n) u(n) and f(n) (v) = z(n) v(n). 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 epsilon X*.
UTU Research Portal