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

DOI10.1007/978-3-642-00982-2_42zbMath1234.68223OpenAlexW2115780545MaRDI QIDQ3618608

Meena Mahajan, Nutan Limaye

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)

Related Items (1)

On the Complexity of Intersecting Regular, Context-Free, and Tree Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Tree-size bounded alternation
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• A polynomial-time parsing algorithm for \(K\)-depth languages
• Visibly pushdown languages
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On the Tape Complexity of Deterministic Context-Free Languages
• 2-Visibly Pushdown Automata
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS

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