2025/06/17 by Antonio Casares, Pierre Ohlmann, Casares, Antonio +5
Arts and Humanities · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Lexicography and Language Studies
paper · pdf · doi:10.48550/arxiv.2506.14544
openalex publication_date 2025/06/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs with neutral transitions. Recently, [Ohlmann, TheoretiCS 2023] established that positionality of prefix-independent objectives is preserved by finite lexicographic products. We propose two different notions of infinite lexicographic products indexed by arbitrary ordinals, and extend Ohlmann's result by proving that they also preserve positionality. In the context of one-player positionality, this extends positional determinacy results of [Grädel and Walukiewicz, Logical Methods in Computer Science 2006] to edge-labelled games and arbitrarily many priorities for both Max-Parity and Min-Parity. Moreover, we show that the Max-Parity objectives over countable ordinals are complete for the infinite levels of the difference hierarchy over Σ02 and that Min-Parity is complete for the class Σ03. We obtain therefore positional languages that are complete for all those levels, as well as new insights about closure under unions and neutral letters.