Communication Dans Un Congrès Année : 2024

Positionality in Σ⁰₂ and a Completeness Result

Résumé

We study the existence of positional strategies for the protagonist in infinite duration games over arbitrary game graphs. We prove that prefix-independent objectives in Σ⁰₂ which are positional and admit a (strongly) neutral letter are exactly those that are recognised by history-deterministic monotone co-Büchi automata over countable ordinals. This generalises a criterion proposed by [Kopczyński, ICALP 2006] and gives an alternative proof of closure under union for these objectives, which was known from [Ohlmann, TheoretiCS 2023]. We then give two applications of our result. First, we prove that the mean-payoff objective is positional over arbitrary game graphs. Second, we establish the following completeness result: for any objective W which is prefix-independent, admits a (weakly) neutral letter, and is positional over finite game graphs, there is an objective W' which is equivalent to W over finite game graphs and positional over arbitrary game graphs.
Fichier principal
Vignette du fichier
LIPIcs.STACS.2024.54.pdf (812.96 Ko) Télécharger le fichier
licence

Dates et versions

hal-04894067 , version 1 (17-01-2025)

Licence

Identifiants

Citer

Pierre Ohlmann, Michał Skrzypczak. Positionality in Σ⁰₂ and a Completeness Result. Symposium on Theoretical Aspects of Computer Science (STACS), 2024, Clermont - Ferrand, France. ⟨10.4230/LIPICS.STACS.2024.54⟩. ⟨hal-04894067⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More