Search

• < Previous
• 1
• Next >

Minimization of visibly pushdown automata is NP-complete

We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such that each language is associated with an initial&nbsp;[&hellip;]