A characterization of positional omega-regular languages

In the context of infinite duration games over graphs, a central question is: For which objectives can the existential player always play optimally using positional (memoryless) strategies? We present a characterization of positionality for the class of omega-regular objectives. Namely, an omega-regular objective is positional if and only if it is recognized by a good-for-games parity automaton admitting a total order over its set of states such that its transitions satisfy some monotonicity properties with respect to this order. Using this characterization, we hope to answer many open questions concerning positionality in the case of omega-regular objectives, including obtaining finite-to-infinite and 1-to-2-players arenas lifts and the closure under union of prefix-independent positional objectives. This talk is based on ongoing work with Pierre Ohlmann. Contributed talk given by Antonio Casares

Authors

• Antonio Casares

Keywords

No keywords are indexed for this paper.