Languages of Boundedly-Ambiguous Vector Addition Systems with States

2025/04/10 by Wojciech Czerwiński, Czerwiński, Wojciech, Łukasz Orlikowski +1 · 1 voice
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL

paper · pdf · doi:10.48550/arxiv.2504.07669

arxiv published 2025/04/10 · arxiv updated 2025/09/15

Abstract

The aim of this paper is to deliver broad understanding of a class of languages of boundedly-ambiguous VASS, that is k-ambiguous VASS 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 VASS and undecidability of the k-ambiguity problem, namely the question whether a given VASS language is a language of some k-ambiguous VASS. Finally, we show that the regularity problem is decidable for k-ambiguous VASS.

Citations

• Factoring through monomial representations: arithmetic characterizations and ambiguity of weighted automata
• On the Separability Problem of VASS Reachability Languages
• History-deterministic Vector Addition Systems
• On History-Deterministic One-Counter Nets
• Computing the linear hull: Deciding Deterministic? and Unambiguous? for weighted automata over fields
• Determinization of One-Counter Nets
• Lower Bounds for Unambiguous Automata via Communication Complexity
• New Techniques for Universality in Unambiguous Register Automata
• Bidimensional linear recursive sequences and universality of unambiguous register automata
• An Approach to Regular Separability in Vector Addition Systems
• The Containment Problem for Unambiguous Register Automata
• A survival guide to presburger arithmetic
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Regular Separability of Well Structured Transition Systems
• Decidability of Weak Simulation on One-counter Nets
• Some decision problems related to the reachability problem for Petri nets
• Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime Factors

Discussions

• Wojciech Czerwi\'nski, {\L}ukasz Orlikowski: Languages of Boundedly-Ambiguous Vector Addition Systems with States https://arxiv.org/abs/2504.07669 https://arxiv.org/pdf/2504.07669 https://arxiv.org/ht [bsky, 0 points, 1 comments]

Related

• Unboundedness problems for languages of vector addition systems
• Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
• Universality Problem for Unambiguous VASS
• An Approach to Regular Separability in Vector Addition Systems
• Techniques for Showing the Decidability of the Boundedness Problem of Language Acceptors