On the Borel Inseparability of Game Tree Languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

On the Borel Inseparability of Game Tree Languages

Résumé

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$.
Fichier principal
Vignette du fichier
hummel_new.pdf (215.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00360184 , version 1 (10-02-2009)

Identifiants

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

Citer

Szczepan Hummel, Henryk Michalewski, Damian Niwinski. On the Borel Inseparability of Game Tree Languages. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.565-576. ⟨inria-00360184⟩

Collections

STACS2009
36 Consultations
70 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More