The Critical Exponent is Computable for Automatic Sequences

DOI10.4204/EPTCS.63.29zbMath1331.11019arXiv1104.2303MaRDI QIDQ2789533

Jeffrey O. Shallit, Luke Schaeffer

Publication date: 1 March 2016

Published in: International Journal of Foundations of Computer Science, Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.2303

zbMATH Keywords

critical exponentautomatic sequencedecision procedurerational numberDiophantine exponent

Mathematics Subject Classification ID

Combinatorics on words (68R15) Recurrences (11B37) Automata sequences (11B85)

Related Items

Automatic Theorem-Proving in Combinatorics on Words ⋮ Decision algorithms for Fibonacci-automatic Words, I: Basic results ⋮ On square factors and critical factors of \(k\)-bonacci words on infinite alphabet ⋮ Automatic Sets of Rational Numbers ⋮ Quadratic approximation to automatic continued fractions ⋮ Frobenius Numbers and Automatic Sequences ⋮ The upper density of an automatic set is rational ⋮ First-Order Logic and Numeration Systems ⋮ Ostrowski-automatic sequences: theory and applications ⋮ Topological conjugacy of constant length substitution dynamical systems

Cites Work

• On critical exponents in fixed points of non-erasing morphisms
• Every real number greater than 1 is a critical exponent
• Numeration systems, linear recurrences, and regular sets
• Thin and slender languages
• Periodicity, repetitions, and orbits of an automatic sequence
• On the expansion of some exponential periods in an integer base
• Morphic and automatic words: maximal blocks and Diophantine approximation
• Diophantine properties of real numbers generated by finite automata
• Initial powers of Sturmian sequences
• H-bounded and semi-discrete languages
• Dynamics forβ-shifts and Diophantine approximation
• On the base-dependence of sets of numbers recognizable by finite automata
• Uniform tag sequences