  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 state
and a set of final states. We show that minimizing immersions is NP-complete,
and reduce this problem to the minimization of visibly pushdown automata.
