On the Borel Inseparability of Game Tree Languages
| dc.creator | Hummel, Szczepan | |
| dc.creator | Michalewski, Henryk | |
| dc.creator | Niwinski, Damian | |
| dc.date | 2009-02-10 | |
| dc.date.accessioned | 2026-07-07T12:39:56Z | |
| dc.date.available | 2026-07-07T12:39:56Z | |
| dc.description | 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 $μ$-calculus and the automata index hierarchies. They showed that separability fails in general for non-deterministic automata of type $Σ^μ_{n} $, starting from level $n=3$, while our result settles the missing case $n=2$. | |
| dc.identifier | https://arxiv.org/abs/0902.1732 | |
| dc.identifier | http://arxiv.org/abs/0902.1732 | |
| dc.identifier | 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 565-576 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219296 | |
| dc.subject | Logic | |
| dc.title | On the Borel Inseparability of Game Tree Languages | |
| dc.type | text |