Explorable Parity Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917102623916032 |
|---|---|
| author | Hazard, Emile Idir, Olivier Kuperberg, Denis |
| author_facet | Hazard, Emile Idir, Olivier Kuperberg, Denis |
| contents | We define the class of explorable automata on finite or infinite words. This is a generalization of History-Deterministic (HD) automata, where this time non-deterministic choices can be resolved by building finitely many simultaneous runs instead of just one. We show that recognizing HD parity automata of fixed index among explorable ones is in PTime, thereby giving a strong link between the two notions. We then show that recognizing explorable automata is ExpTime-complete, in the case of finite words or parity automata up to index [0, 2]. Additionally, we define the notion of ω-explorable automata on infinite words, where countably many runs can be used to resolve the non-deterministic choices. We show ExpTime-completeness for ω-explorability of automata on infinite words for the safety and coBüchi acceptance conditions. We finally characterize the expressivity of (ω-)explorable automata with respect to the parity index hierarchy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23187 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Explorable Parity Automata Hazard, Emile Idir, Olivier Kuperberg, Denis Formal Languages and Automata Theory We define the class of explorable automata on finite or infinite words. This is a generalization of History-Deterministic (HD) automata, where this time non-deterministic choices can be resolved by building finitely many simultaneous runs instead of just one. We show that recognizing HD parity automata of fixed index among explorable ones is in PTime, thereby giving a strong link between the two notions. We then show that recognizing explorable automata is ExpTime-complete, in the case of finite words or parity automata up to index [0, 2]. Additionally, we define the notion of ω-explorable automata on infinite words, where countably many runs can be used to resolve the non-deterministic choices. We show ExpTime-completeness for ω-explorability of automata on infinite words for the safety and coBüchi acceptance conditions. We finally characterize the expressivity of (ω-)explorable automata with respect to the parity index hierarchy. |
| title | Explorable Parity Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2410.23187 |