Nie jesteś zalogowany |
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
- 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.
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.
