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 exponent; automatic sequence; decision procedure; rational number; Diophantine exponent

Mathematics Subject Classification ID

68R15: Combinatorics on words

11B37: Recurrences

11B85: Automata sequences

Related Items

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

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