Positional $ω$-regular languages
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_ | 1866917328665444352 |
|---|---|
| author | Casares, Antonio Ohlmann, Pierre |
| author_facet | Casares, Antonio Ohlmann, Pierre |
| contents | In the context of two-player games over graphs, a language $L$ is called positional if, in all games using $L$ as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history of the play. In this work, we describe the class of parity automata recognising positional languages, providing a complete characterisation of positionality for $ω$-regular languages. As corollaries, we establish decidability of positionality in polynomial time, finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent positional objectives, answering a conjecture by Kopczyński in the $ω$-regular case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15384 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Positional $ω$-regular languages Casares, Antonio Ohlmann, Pierre Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science 68Q45 F.4.3 In the context of two-player games over graphs, a language $L$ is called positional if, in all games using $L$ as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history of the play. In this work, we describe the class of parity automata recognising positional languages, providing a complete characterisation of positionality for $ω$-regular languages. As corollaries, we establish decidability of positionality in polynomial time, finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent positional objectives, answering a conjecture by Kopczyński in the $ω$-regular case. |
| title | Positional $ω$-regular languages |
| topic | Formal Languages and Automata Theory Computer Science and Game Theory Logic in Computer Science 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2401.15384 |