A note on two-way nondeterministic pushdown automata

DOI10.1016/0020-0190(82)90075-8zbMath0496.68035OpenAlexW2073767883MaRDI QIDQ1170034

Wojciech Rytter

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90075-8

zbMATH Keywords

time complexityrandom access machinecomplexity of the simulation of pushdown automataone-turnreversal boundedstack bounded

Mathematics Subject Classification ID

Related Items (3)

Alternating multihead finite automata ⋮ Time complexity of loop-free two-way pushdown automata ⋮ On efficient recognition of transductions and relations

Cites Work

• Unnamed Item
• Time complexity of languages recognized by one-way multihead pushdown automata
• General context-free recognition in less than cubic time
• On the Asymptotic Complexity of Matrix Multiplication
• Time and tape complexity of pushdown automaton languages

This page was built for publication: A note on two-way nondeterministic pushdown automata