Two-way nested stack automata are equivalent to two-way stack automata

DOI10.1016/S0022-0000(75)80004-3zbMath0331.68029OpenAlexW2063441619WikidataQ29026172 ScholiaQ29026172MaRDI QIDQ1227452

Catriel Beeri

Publication date: 1975

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(75)80004-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (4)

The IO- and OI-hierarchies ⋮ Tree-stack automata ⋮ Iterated stack automata and complexity classes ⋮ Two-way nested stack automata are equivalent to two-way stack automata

Cites Work

• Two-way nested stack automata are equivalent to two-way stack automata
• Nonerasing stack automata
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Intercalation theorems for stack languages
• Multi-tape and multi-head pushdown automata
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• Halting Stack Automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Two-way nested stack automata are equivalent to two-way stack automata