A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
On the Periodicity of Morphic Words
Tekijät: Harju, Tero; Halava, Vesa; Kärki, Tomi; Rigo, Michel
Julkaisuvuosi: 2010
Journal: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: DEVELOPMENTS IN LANGUAGE THEORY
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 6224
Aloitussivu: 209
Lopetussivu: 217
Sivujen määrä: 9
ISBN: 978-3-642-14454-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-14455-4_20
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali