On the complexity of membership and counting in height-deterministic pushdown automata

DOI10.25596/JALC-2009-211MaRDI QIDQ3589625zbMATH OpenFDO

Authors Nutan Limaye, Meena Mahajan, Antoine Meyer

Publication date 20 September 2010

Full work available at URL https://doi.org/10.25596/JALC-2009-211

zbMATH Keywords

visibly pushdown automatavisibly pushdown languages

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Height-Deterministic Pushdown Automata
• Visibly pushdown automata and transducers with counters
• Efficient determinization of visibly and height-deterministic pushdown automata
• On the Membership Problem for Visibly Pushdown Languages

Cited in

(7)

• Efficient determinization of visibly and height-deterministic pushdown automata
• Counting paths in VPA is complete for \(\#\mathrm{NC}^1\)
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Height-Deterministic Pushdown Automata
• Counting paths in VPA is complete for \#NC\(^{1}\)
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Pushdown automata and constant height: decidability and bounds

This page was built for publication: On the complexity of membership and counting in height-deterministic pushdown automata

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