A simulation result for two-way pushdown automata

DOI10.1016/0020-0190(83)90124-2zbMath0511.68054OpenAlexW2071689556MaRDI QIDQ1838834

Wojciech Rytter

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(83)90124-2

zbMATH Keywords

algorithmsimulationtime and space complexitylanguages recognized by two-way deterministic pushdown automata

Mathematics Subject Classification ID

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

Related Items (2)

Maximally-Polyvariant Partial Evaluation in Polynomial Time ⋮ A Practical Simulation Result for Two-Way Pushdown Automata

Cites Work

• An effective simulation of deterministic pushdown automata with many two- way and one-way heads
• Storage Modification Machines
• Time and tape complexity of pushdown automaton languages
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simulation result for two-way pushdown automata