On Recognizable Tree Languages Beyond the Borel Hierarchy

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 ⩾ 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 _{(&inodot;,κ)} , 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 _{(&inodot;,κ)} for κ−ı⩾ 2. In particular these languages W _{(&inodot;,κ)} are not in any class D _{α} (Σ ^1_1 ) for α<ω ^{ω} .

Keywords

Infinite trees tree automaton regular tree language Cantor topology topological complexity Borel hierarchy difference hierarchy of analytic sets complete sets unambiguous tree automaton game tree language