Deterministic Parikh automata on infinite words
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914808987648000 |
|---|---|
| author | Grobler, Mario Siebertz, Sebastian |
| author_facet | Grobler, Mario Siebertz, Sebastian |
| contents | Various variants of Parikh automata on infinite words have recently been introduced in the literature. However, with some exceptions only their non-deterministic versions have been considered. In this paper we study the deterministic versions of all variants of Parikh automata on infinite words that have not yet been studied. We compare the expressiveness of the deterministic models and investigate their closure properties and decision problems with applications to model checking. The model of deterministic limit Parikh automata turns out to be most interesting, as it is the only deterministic Parikh model generalizing the $ω$-regular languages, the only deterministic Parikh model closed under the Boolean operations and the only deterministic Parikh model for which all common decision problems are decidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14737 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic Parikh automata on infinite words Grobler, Mario Siebertz, Sebastian Formal Languages and Automata Theory Various variants of Parikh automata on infinite words have recently been introduced in the literature. However, with some exceptions only their non-deterministic versions have been considered. In this paper we study the deterministic versions of all variants of Parikh automata on infinite words that have not yet been studied. We compare the expressiveness of the deterministic models and investigate their closure properties and decision problems with applications to model checking. The model of deterministic limit Parikh automata turns out to be most interesting, as it is the only deterministic Parikh model generalizing the $ω$-regular languages, the only deterministic Parikh model closed under the Boolean operations and the only deterministic Parikh model for which all common decision problems are decidable. |
| title | Deterministic Parikh automata on infinite words |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2401.14737 |