• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Periodicity of Morphic Words

Vesa Halava, Tero Harju, Tomi Kärki, Michel Rigo (Eds.), On the Periodicity of Morphic Words , Lecture Notes in Computer Science 6224, Springer-Verlag, 2010.

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^ω(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.

BibTeX entry:

@PROCEEDINGS{pHaHaK,
  title = {On the Periodicity of Morphic Words },
  volume = {6224},
  series = {Lecture Notes in Computer Science},
  editor = {Halava, Vesa and Harju, Tero and Kärki, Tomi and Rigo, Michel},
  publisher = {Springer-Verlag},
  year = {2010},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication