A4 Refereed article in a conference publication
On the Periodicity of Morphic Words
Authors: Harju, Tero; Halava, Vesa; Kärki, Tomi; Rigo, Michel
Publication year: 2010
Journal: Lecture Notes in Computer Science
Journal name in source: DEVELOPMENTS IN LANGUAGE THEORY
Journal acronym: LECT NOTES COMPUT SC
Volume: 6224
First page : 209
Last page: 217
Number of pages: 9
ISBN: 978-3-642-14454-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-14455-4_20
Abstract
Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word h(omega) (a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable.
Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word h(omega) (a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable.
UTU Research Portal