Time complexity of loop-free two-way pushdown automata

DOI10.1016/0020-0190(83)90063-7MaRDI QIDQ1838833zbMATH OpenOpenAlexFDO

Authors 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)90063-7

zbMATH Keywords

algorithm for the fast recognition of languages recognized by two-way nondeterministic pushdown automatasimulationtime complexity

Mathematics Subject Classification ID

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

Cites work

• A note on two-way nondeterministic pushdown automata
• An effective simulation of deterministic pushdown automata with many two- way and one-way heads
• General context-free recognition in less than cubic time
• scientific article; zbMATH DE number 3731318 (Why is no real title available?)
• scientific article; zbMATH DE number 3573276 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Improving programs by the introduction of recursion
• Time and tape complexity of pushdown automaton languages

This page was built for publication: Time complexity of loop-free two-way pushdown automata

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