Transition-based vs stated-based acceptance for automata over infinite words
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915502964604928 |
|---|---|
| author | Casares, Antonio |
| author_facet | Casares, Antonio |
| contents | Automata over infinite objects are a well-established model with applications in logic and formal verification. Traditionally, acceptance in such automata is defined based on the set of states visited infinitely often during a run. However, there is a growing trend towards defining acceptance based on transitions rather than states.
In this survey, we analyse the reasons for this shift and advocate using transition-based acceptance in the context of automata over infinite words. We present a collection of problems where the choice of formalism has a major impact and discuss the causes of these differences. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_15402 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Transition-based vs stated-based acceptance for automata over infinite words Casares, Antonio Formal Languages and Automata Theory Logic in Computer Science 68Q45 F.4.3 Automata over infinite objects are a well-established model with applications in logic and formal verification. Traditionally, acceptance in such automata is defined based on the set of states visited infinitely often during a run. However, there is a growing trend towards defining acceptance based on transitions rather than states. In this survey, we analyse the reasons for this shift and advocate using transition-based acceptance in the context of automata over infinite words. We present a collection of problems where the choice of formalism has a major impact and discuss the causes of these differences. |
| title | Transition-based vs stated-based acceptance for automata over infinite words |
| topic | Formal Languages and Automata Theory Logic in Computer Science 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2508.15402 |