Periodicity, repetitions, and orbits of an automatic sequence

JP Allouche, N Rampersad, J Shallit - Theoretical Computer Science, 2009 - Elsevier
JP Allouche, N Rampersad, J Shallit
Theoretical Computer Science, 2009Elsevier
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 …
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.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果