An algebraic characterisation of Eve-positional languages
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911621597626368 |
|---|---|
| author | Colcombet, Thomas Idir, Olivier |
| author_facet | Colcombet, Thomas Idir, Olivier |
| contents | We present a new algebraic characterisation of Eve-positionality for $ω$-regular languages. It involves only a limited number of elementary local properties to be checked.
An $ω$-regular language is Eve-positional if, in all games with this language as objective, the existential player (Eve) can play optimally without keeping any information concerning the history of the moves seen so far. This notion plays a crucial role in verification, automata theory and synthesis.
Our proof heavily relies on a recent result of Casares and Ohlmann which states several characterisations of Eve-positionality for $ω$-regular languages. More precisely, it relies on their a 1-to-2 player lift result: for an $ω$-regular language, being Eve-positionally over all finite Eve-only arenas suffices for being Eve-positional over all two-player arenas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22648 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An algebraic characterisation of Eve-positional languages Colcombet, Thomas Idir, Olivier Formal Languages and Automata Theory 68Q45 F.4.3 We present a new algebraic characterisation of Eve-positionality for $ω$-regular languages. It involves only a limited number of elementary local properties to be checked. An $ω$-regular language is Eve-positional if, in all games with this language as objective, the existential player (Eve) can play optimally without keeping any information concerning the history of the moves seen so far. This notion plays a crucial role in verification, automata theory and synthesis. Our proof heavily relies on a recent result of Casares and Ohlmann which states several characterisations of Eve-positionality for $ω$-regular languages. More precisely, it relies on their a 1-to-2 player lift result: for an $ω$-regular language, being Eve-positionally over all finite Eve-only arenas suffices for being Eve-positional over all two-player arenas. |
| title | An algebraic characterisation of Eve-positional languages |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3 |
| url | https://arxiv.org/abs/2604.22648 |