2026-07-24T00:57:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1849 2024-03-06T10:33:13Z ddc:004 open_access

On the Borel Inseparability of Game Tree Languages Hummel, Szczepan Michalewski, Henryk Niwinski, Damian Tree automata Separation property Borel sets Parity games 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$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Szczepan Hummel and Henryk Michalewski and Damian Niwinski 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1849 urn:nbn:de:0030-drops-18493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1849 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode