New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines

DOI10.1016/j.ic.2023.105027OpenAlexW4360604354MaRDI QIDQ6040662

Oscar H. Ibarra, Ian McQuillan

Publication date: 19 May 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2023.105027

zbMATH Keywords

Turing machinescomplexity classesstack automatachecking stack automataelementary languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Two-way automata with more than one storage medium
• Iterated stack automata and complexity classes
• On store languages of language acceptors
• Automata equipped with auxiliary data structures and regular realizability problems
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Fast Pattern Matching in Strings
• An Approach to a Unified Theory of Automata
• Two-way pushdown automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Variations of checking stack automata: obtaining unexpected decidability properties
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• Unnamed Item
• Unnamed Item

This page was built for publication: New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines