Generalizations of Checking Stack Automata: Characterizations and Hierarchies

DOI10.1142/S0129054121410045MaRDI QIDQ6114832zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Ian McQuillan

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054121410045

zbMATH Keywords

characterizationshierarchiesmulti-head finite automatachecking stack automataspace-bounded Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Classical models of computation (Turing machines, etc.) (68Q04)

Recommendations

• Generalizations of checking stack automata: characterizations and hierarchies
• The power of two-way deterministic checking stack automata
• Alternating Pushdown and Stack Automata
• Some characterizations of multihead finite automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3690693 (Why is no real title available?)
• scientific article; zbMATH DE number 3461491 (Why is no real title available?)
• A Note Concerning Nondeterministic Tape Complexities
• A note on undecidable properties of formal languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Checking automata and one-way stack languages
• Generalizations of checking stack automata: characterizations and hierarchies
• On the computational power of pushdown automata
• On two-way multihead automata
• One-way stack automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Relating refined space complexity classes
• Space complexity of stack automata models
• Stack automata and compiling
• Stack languages and log n space
• The power of two-way deterministic checking stack automata
• Transformational methods and their application to complexity problems
• Two-way automata with more than one storage medium

Cited in

(10)

• Generalizations of checking stack automata: characterizations and hierarchies
• The power of two-way deterministic checking stack automata
• Space complexity of stack automata models
• New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
• Deterministic real-time tree-walking-storage automata
• Tree-walking-storage automata
• Deterministic tree-walking-storage automata
• Space Complexity of Stack Automata Models
• The design of checkable automata. II
• Deterministic real-time tree-walking-storage automata

This page was built for publication: Generalizations of Checking Stack Automata: Characterizations and Hierarchies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6114832)