On the Periodicity of Morphic Words



: Harju, Tero; Halava, Vesa; Kärki, Tomi; Rigo, Michel

: 2010

: Lecture Notes in Computer Science

: DEVELOPMENTS IN LANGUAGE THEORY

: LECT NOTES COMPUT SC

: 6224

: 209

: 217

: 9

: 978-3-642-14454-7

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-14455-4_20


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.



Last updated on 2024-26-11 at 13:14