A characterization of half-positionality for omega-regular languages

Prelegent(ci)

Antonio Casares

Afiliacja

University of Warsaw

Termin

6 grudnia 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---