Emptiness of alternating tree automata through games of imperfect information

Prelegent(ci)

Nathanaël Fijalkow

Afiliacja

Uniwersytet Warszawski

Termin

20 marca 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Sophie Pinchinat and Olivier Serre

Seminarium

Seminarium „Teoria automatów”

---

In this talk, I will consider the emptiness problem for alternating tree automata with two different acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted).

I will show a new approach to tackle these problems, through games of imperfect information, and argue that this technique provides new answers as well as new questions: first, it shows the decidability of the emptiness problem for alternating (Buechi) tree automata with qualitative semantics, and second, it is generic in the sense that it only relies on a positionality result and decidability of the corresponding imperfect information games.

---