On Recognizable Tree Languages Beyond the Borel Hierarchy.

Authors: Olivier Finkel, Pierre Simonnet
Subjects: Logic
link: http://arxiv.org/abs/0909.0393
Abstract

We investigate the topological complexity of non Borel recognizable tree
languages with regard to the difference hierarchy of analytic sets. We show
that, for each integer $n \geq 1$, there is a $D_{\omega^n}({\bf
\Sigma}^1_1)$-complete tree language L_n accepted by a (non deterministic)
Muller tree automaton. On the other hand, we prove that a tree language
accepted by an unambiguous B\"uchi tree automaton must be Borel. Then we
consider the game tree languages $W_{(i,k)}$, for Mostowski-Rabin indices $(i,
k)$. We prove that the $D_{\omega^n}({\bf \Sigma}^1_1)$-complete tree languages
L_n are Wadge reducible to the game tree language $W_{(i, k)}$ for $k-i \geq
2$. In particular these languages $W_{(i, k)}$ are not in any class
$D_{\alpha}({\bf \Sigma}^1_1)$ for $\alpha < \omega^\omega$.