Wojciech Czerwiński ; Piotr Hofman - Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable

lmcs:11165 - Logical Methods in Computer Science, March 20, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:27)2025
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is DecidableArticle

Authors: Wojciech Czerwiński ; Piotr Hofman

    We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASS) with the acceptance condition defined by the set of accepting states (and more generally by some upward-closed conditions). In general, the problem of language equivalence is undecidable even for one-dimensional VASS, thus to get decidability we investigate restricted subclasses. On the one hand, we show that the problem of language inclusion of a VASS in k-ambiguous VASS (for any natural k) is decidable and even in Ackermann. On the other hand, we prove that the language equivalence problem is already Ackermann-hard for deterministic VASS. These two results imply Ackermann-completeness for language inclusion and equivalence in several possible restrictions. Some of our techniques can be also applied in much broader generality in infinite-state systems, namely for some subclass of well-structured transition systems.


    Volume: Volume 21, Issue 1
    Published on: March 20, 2025
    Accepted on: February 7, 2025
    Submitted on: April 7, 2023
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 251 times.
    This article's PDF has been downloaded 101 times.