Periodicity, repetitions, and orbits of an automatic sequence

We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given k -automatic sequence is ultimately periodic. We prove that it is decidable whether a given k -automa...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-08, Vol.410 (30), p.2795-2803
Main Authors: Allouche, Jean-Paul, Rampersad, Narad, Shallit, Jeffrey
Format: Article
Language:English
Subjects:
Automatic sequence
Continued fraction
Decidability
Orbit
Orbit closure
Overlap-free
Periodicity
Rudin–Shapiro sequence
Squarefree
Thue–Morse sequence
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given k -automatic sequence is ultimately periodic. We prove that it is decidable whether a given k -automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a k -automatic sequence is k -automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope α , have automatic continued fraction expansions if α does.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.02.006