On the Borel Inseparability of Game Tree Languages

Abstract : The game tree languages can be viewed as an automata-theoretic counterpart of parity games on graphs. They witness the strictness of the index hierarchy of alternating tree automata, as well as the fixed-point hierarchy over binary trees. We consider a game tree language of the first non-trivial level, where Eve can force that 0 repeats from some moment on, and its dual, where Adam can force that 1 repeats from some moment on. Both these sets (which amount to one up to an obvious renaming) are complete in the class of co-analytic sets. We show that they cannot be separated by any Borel set, hence {\em a fortiori\/} by any weakly definable set of trees. This settles a case left open by L.Santocanale and A.Arnold, who have thoroughly investigated the separation property within the $\mu$-calculus and the automata index hierarchies. They showed that separability fails in general for non-deterministic automata of type $\Sigma^{\mu }_{n}$, starting from level $n=3$, while our result settles the missing case $n=2$.
Keywords :
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.565-576, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Domaine :

Littérature citée [18 références]

https://hal.inria.fr/inria-00360184
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 15:47:26
Dernière modification le : vendredi 13 février 2009 - 12:09:58
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:37:45

Fichiers

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

Identifiants

• HAL Id : inria-00360184, version 1
• ARXIV : 0902.1732

Citation

Szczepan Hummel, Henryk Michalewski, Damian Niwinski. On the Borel Inseparability of Game Tree Languages. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.565-576, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360184〉

Métriques

Consultations de la notice

73

Téléchargements de fichiers