Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata

DOI10.1007/978-3-642-00982-2_42MaRDI QIDQ3618608zbMATH OpenOpenAlexFDO

Authors Nutan Limaye, Meena Mahajan

Publication date 2 April 2009

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00982-2_42

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A unifying approach for multistack pushdown automata
• Ordered multi-stack visibly pushdown automata
• From multi to single stack automata
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata

Cites work

• 2-Visibly Pushdown Automata
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• A polynomial-time parsing algorithm for \(K\)-depth languages
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 522856 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On the Tape Complexity of Deterministic Context-Free Languages
• Tree-size bounded alternation
• Visibly pushdown languages

Cited in

(6)

• A unifying approach for multistack pushdown automata
• Ordered multi-stack visibly pushdown automata
• On the complexity of intersecting regular, context-free, and tree languages
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• From multi to single stack automata
• Testing membership in parenthesis languages

This page was built for publication: Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata

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