Olivier Gauwin ; Anca Muscholl ; Michael Raskin - 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-completeArticle

Authors: Olivier Gauwin ; Anca Muscholl ; Michael Raskin ORCID

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.

https://doi.org/10.23638/LMCS-16(1:14)2020
Source: arXiv.org:1907.09563
Volume: Volume 16, Issue 1
Published on: February 13, 2020
Accepted on: December 19, 2019
Submitted on: July 24, 2019
Keywords: Computer Science - Formal Languages and Automata Theory
Licence: Attribution 4.0 International (CC BY 4.0)
Funding:
    Source : OpenAIRE Graph
  • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 2570 times.
This article's PDF has been downloaded 735 times.