A characterization of half-positionality for omega-regular languages

Speaker(s)

Antonio Casares

Affiliation

University of Warsaw

Date

Dec. 6, 2023, 2:15 p.m.

Room

room 5050

Seminar

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.

---