Gauwin, Olivier and Muscholl, Anca and Raskin, Michael - Minimization of visibly pushdown automata is NP-complete

lmcs:5640 - Logical Methods in Computer Science, February 13, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:14)2020
Minimization of visibly pushdown automata is NP-complete

Authors: Gauwin, Olivier and Muscholl, Anca and Raskin, Michael

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.


Volume: Volume 16, Issue 1
Published on: February 13, 2020
Submitted on: July 24, 2019
Keywords: Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 115 times.
This article's PDF has been downloaded 75 times.