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

    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
    Accepted on: December 19, 2019
    Submitted on: July 24, 2019
    Keywords: Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    Consultation statistics

    This page has been seen 1001 times.
    This article's PDF has been downloaded 419 times.