On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts

DOI10.1016/j.tcs.2009.06.037zbMath1191.68344OpenAlexW2081898945MaRDI QIDQ1034609

Jakob Grue Simonsen

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.06.037

zbMATH Keywords

computational complexitysymbolic dynamicsbeta-shiftscomplexity hierarchies

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Theory of software (68N99)

Related Items

Beta-shifts, their languages, and computability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Space hierarchy theorem revised.
• Forbidden words in symbolic dynamics
• Measures of maximal entropy for random \(\beta\)-expansions
• \(\beta\)-expansions and symbolic dynamics
• Relationships between nondeterministic and deterministic tape complexities
• A Note on Sparse Complete Sets
• Finite beta-expansions
• On theβ-expansions of real numbers
• Symbolic dynamics for $\beta$-shifts and self-normal numbers
• An Introduction to Symbolic Dynamics and Coding
• Mathematical Foundations of Computer Science 2005