Languages of Boundedly-Ambiguous Vector Addition Systems with States
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909787696922624 |
|---|---|
| author | Czerwiński, Wojciech Orlikowski, Łukasz |
| author_facet | Czerwiński, Wojciech Orlikowski, Łukasz |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_07669 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Languages of Boundedly-Ambiguous Vector Addition Systems with States Czerwiński, Wojciech Orlikowski, Łukasz Formal Languages and Automata Theory 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. |
| title | Languages of Boundedly-Ambiguous Vector Addition Systems with States |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2504.07669 |