You are not logged in | Log in

A characterization of half-positionality for omega-regular languages

Antonio Casares
University of Warsaw
Dec. 6, 2023, 2:15 p.m.
room 5050
Seminar Automata Theory

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? In this talk, we characterize omega-regular objectives with this property. Using this characterization, we obtain decidability of half-positionality in polynomial time, get finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent half-positional objectives, answering a conjecture by Kopczyński. This is joint work with Pierre Ohlmann.