Emptiness Of Alternating Tree Automata Using Games With Imperfect Information

Abstract : We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known. We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.
Type de document :
Communication dans un congrès
33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013), 2013, Guwahati, India. LLIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 24, pp.13, Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013). 〈10.4230/LIPIcs.FSTTCS.2013.299〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01260682
Contributeur : Olivier Serre <>
Soumis le : vendredi 22 janvier 2016 - 14:52:27
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : samedi 23 avril 2016 - 10:46:26

Fichier

FPS13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Nathanaël Fijalkow, Sophie Pinchinat, Olivier Serre. Emptiness Of Alternating Tree Automata Using Games With Imperfect Information. 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013), 2013, Guwahati, India. LLIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 24, pp.13, Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS 2013). 〈10.4230/LIPIcs.FSTTCS.2013.299〉. 〈hal-01260682〉

Partager

Métriques

Consultations de la notice

340

Téléchargements de fichiers

107