Nie jesteś zalogowany | Zaloguj się

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.