The power of two-way deterministic checking stack automata

DOI10.1016/0890-5401(89)90015-1zbMath0744.68042OpenAlexW2003560161MaRDI QIDQ1812540

Joost Engelfriet

Publication date: 25 June 1992

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

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90015-1

zbMATH Keywords

checking stack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Space Complexity of Stack Automata Models ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Variations of checking stack automata: obtaining unexpected decidability properties ⋮ Space Complexity of Stack Automata Models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extended macro grammars and stack controlled machines
• Tree transducers, L systems, and two-way machines
• One way finite visit automata
• Checking automata and one-way stack languages
• A characterization of two-way deterministic classes of languages
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Some characterizations of multihead finite automata
• Stack Machines and Classes of Nonnested Macro Languages
• Visits, crosses, and reversals for nondeterministic off-line machines
• An Approach to a Unified Theory of Automata
• A general theory of translation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: The power of two-way deterministic checking stack automata