joint work with Sophie Pinchinat and Olivier Serre

Speaker(s)

Nathanaël Fijalkow

Affiliation

Uniwersytet Warszawski

Date

March 20, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Emptiness of alternating tree automata through games of imperfect information

Seminar

Seminar Automata Theory

---

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.

---