On Recognizable Tree Languages Beyond the Borel Hierarchy
Olivier Finkel, Pierre Simonnet · Fundamenta Informaticae · 2009
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 ⩾ 1, there is a D _{ω^n} (Σ ^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üchi tree automaton must be Borel. Then we consider the game tree languages W _{(ı,κ)} , for Mostowski-Rabin indices (ıκ). We prove that the D _{ω^n} (Σ ^1_1 )-complete tree languages L _n are Wadge reducible to the game tree language W _{(ı,κ)} for κ−ı⩾ 2. In particular these languages W _{(ı,κ)} are not in any class D _{α} (Σ ^1_1 ) for α<ω ^{ω} .