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

    Share and export

    Consultation statistics

    This page has been seen 1093 times.
    This article's PDF has been downloaded 431 times.