On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata

DOI10.1007/978-3-540-79709-8_25zbMath1142.68424OpenAlexW1602383402MaRDI QIDQ3503642

Antoine Meyer, Meena Mahajan, Nutan Limaye

Publication date: 5 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79709-8_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Operator precedence and the visibly pushdown property ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

Cites Work

• Some subclasses of context-free languages in \(NC^ 1\)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Nondeterministic \(NC^1\) computation
• Height-Deterministic Pushdown Automata
• Visibly pushdown languages
• Arithmetizing Classes Around NC 1 and L
• Adding Nesting Structure to Words
• Synchronization of Pushdown Automata
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On the Tape Complexity of Deterministic Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata