A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A periodicity property of iterated morphisms
Tekijät: Honkala J
Kustantaja: EDP SCIENCES S A
Julkaisuvuosi: 2007
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Vuosikerta: 41
Numero: 2
Aloitussivu: 215
Lopetussivu: 223
Sivujen määrä: 9
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita200716
Tiivistelmä
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*.
Turun yliopiston Tutkimustietojärjestelmän portaali