2026-07-27T21:43:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19764 2024-03-11T06:37:05Z ddc:004 open_access

Positionality in Σ⁰₂ and a Completeness Result Ohlmann, Pierre Skrzypczak, Michał infinite duration games positionality Borel class Σ⁰₂ history determinism 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Ohlmann and Michał Skrzypczak 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.54 urn:nbn:de:0030-drops-197643 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.54 eng https://creativecommons.org/licenses/by/4.0/legalcode