Infinite lexicographic products of positional objectives
For researchers in infinite games and automata theory, this provides a theoretical extension of positional determinacy results to infinite products, offering new complete languages for levels of the difference hierarchy.
This paper extends the preservation of positionality from finite to infinite lexicographic products of prefix-independent objectives, proving that infinite lexicographic products indexed by arbitrary ordinals preserve positionality. It also establishes completeness results for Max-Parity and Min-Parity objectives over countable ordinals in the difference hierarchy.
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 $Σ^0_2$ and that Min-Parity is complete for the class $Σ^0_3$. We obtain therefore positional languages that are complete for all those levels, as well as new insights about closure under unions and neutral letters.