1. Minimization of visibly pushdown automata is NP-complete
- Author
-
Olivier Gauwin, Anca Muscholl, and Michael Raskin
- Subjects
computer science - formal languages and automata theory ,Logic ,BC1-199 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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.
- Published
- 2020
- Full Text
- View/download PDF