P-hardness of the emptiness problem for visibly pushdown languages

DOI10.1016/j.ipl.2010.12.013zbMath1260.68181OpenAlexW1976921957MaRDI QIDQ1944895

Martin Lange

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.12.013

zbMATH Keywords

complexityformal languages

Mathematics Subject Classification ID

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

Related Items (2)

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Digging input-driven pushdown automata

Cites Work

• Visibly pushdown languages
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: P-hardness of the emptiness problem for visibly pushdown languages