On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited
From MaRDI portal
Publication:4960229
DOI10.1090/tran/7915zbMath1441.11048arXiv1601.02771OpenAlexW2963443970WikidataQ127460145 ScholiaQ127460145MaRDI QIDQ4960229
Marion Le Gonidec, Boris Adamczewski, Julien Cassaigne
Publication date: 9 April 2020
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.02771
Combinatorics on words (68R15) Formal languages and automata (68Q45) Transcendence (general theory) (11J81) Automata sequences (11B85) Schmidt Subspace Theorem and applications (11J87)
Related Items
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents, Mahler's method
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Substitutions in dynamics, arithmetics and combinatorics
- On the complexity of a family of \(k\)-context-free sequences
- On some questions regarding \(k\)-regular and \(k\)-context-free sequences
- Substitution dynamical systems. Spectral analysis
- Transcendence measures for continued fractions involving repetitive or symmetric patterns
- An explicit lower bound for the block complexity of an algebraic number
- Theta functions and transcendence
- Transcendence of Jacobi's theta series
- On the complexity of algebraic numbers
- On the complexity of algebraic numbers. II: Continued fractions
- On the complexity of algebraic numbers. I: Expansions in integer bases
- On the expansion of some exponential periods in an integer base
- Context-Free Sequences
- Nombres réels de complexité sous-linéaire : mesures d'irrationalité et de transcendance
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- Diophantine properties of real numbers generated by finite automata
- Groupes de Galois et nombres automatiques
- Drunken man infinite words complexity
- Mesures de transcendance et aspects quantitatifs de la méthode de Thue-Siegel-Roth-Schmidt
- On the Complexity of Familiar Functions and Numbers
- Modular functions and transcendence questions
- Automatic Sequences
- Zur Approximation der Exponentialfunktion und des Logarithmus. Teil II.
- On the Computational Complexity of Algorithms
- Méthode de Mahler : relations linéaires, transcendance et applications aux nombres automatiques
- Factor complexity
- Automatic continued fractions are transcendental or quadratic
- Dynamics forβ-shifts and Diophantine approximation
- Three models for the description of language
- Uniform tag sequences
- On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
- Symbolic Dynamics
