2026-07-23T18:19:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23963 2025-11-12T13:25:04Z ddc:004 open_access

Languages of Boundedly-Ambiguous Vector Addition Systems with States Czerwiński, Wojciech Orlikowski, Łukasz vector addition systems Petri nets unambiguity bounded-ambiguity languages The aim of this paper is to deliver broad understanding of a class of languages of boundedly-ambiguous VASSs, that is k-ambiguous VASSs for some natural k. These are languages of Vector Addition Systems with States with the acceptance condition defined by the set of accepting states such that each accepted word has at most k accepting runs. We develop tools for proving that a given language is not accepted by any k-ambiguous VASS. Using them we show a few negative results: lack of some closure properties of languages of k-ambiguous VASSs and undecidability of the k-ambiguity problem, namely the question whether a given VASS language is a language of some k-ambiguous VASS. In fact we show an even more general undecidability result stating that for any class containing all regular languages and only k-ambiguous VASS languages for some k ∈ ℕ it is undecidable whether a language of a given 1-dimensional VASS belongs to this class. Finally, we show that the regularity problem is decidable for k-ambiguous VASSs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Łukasz Orlikowski 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.13 urn:nbn:de:0030-drops-239635 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode