Periodicity, repetitions, and orbits of an automatic sequence

Details Periodicity, repetitions, and orbits of an automatic sequence Periodicity, repetitions, and orbits of an automatic sequence

2008-08-12

arxiv.org/abs/0808.1657v3

Computer Science

Discrete Mathematics

preliminary version

Scientific paper

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 squareefree, 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 alpha, have automatic continued fraction expansions if alpha does.

Affiliated with

Also associated with

No associations

Rating

Periodicity, repetitions, and orbits of an automatic sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Periodicity, repetitions, and orbits of an automatic sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Periodicity, repetitions, and orbits of an automatic sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-202908