You are not logged in |
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
- 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.
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.
