2016/01/12 by Marion Le Gonidec, Adamczewski, Boris, Boris Adamczewski +3
Computer Science · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic, programming, and type systems #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1601.02771
openalex publication_date 2016/01/12 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We consider the complexity of integer base expansions of algebraic irrational\nnumbers from a computational point of view. We show that the Hartmanis--Stearns\nproblem can be solved in a satisfactory way for the class of multistack\nmachines. In this direction, our main result is that the base-b expansion of\nan algebraic irrational real number cannot be generated by a deterministic\npushdown automaton. We also confirm an old claim of Cobham proving that such\nnumbers cannot be generated by a tag machine with dilation factor larger than\none.\n