Pierre Ohlmann ; Michał Skrzypczak - Positionality in $Σ_0^2$ and a completeness result

lmcs:14054 - Logical Methods in Computer Science, April 29, 2026, Volume 22, Issue 2 - https://doi.org/10.46298/lmcs-22(2:10)2026
Positionality in $Σ_0^2$ and a completeness resultArticle

Authors: Pierre Ohlmann ; Michał Skrzypczak

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 $Σ_0^2$ which are positional and admit a (strongly) neutral letter are exactly those that are recognised by history-deterministic monotone co-Bchi 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.


Volume: Volume 22, Issue 2
Secondary volumes: Selected Papers of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) - Track B
Published on: April 29, 2026
Accepted on: February 15, 2026
Submitted on: August 13, 2024
Keywords: Logic in Computer Science