On Recognizable Tree Languages Beyond the Borel Hierarchy

Article type: Research Article

Authors: Finkel, Olivier | Simonnet, Pierre

Affiliations: Equipe de Logique Mathématique CNRS et Université Paris 7, France. E-mail: [email protected] | Systèmes physiques pour l'environnement, Faculté des Sciences, Université de Corse Quartier Grossetti BP52 20250, Corte, France. E-mail: [email protected]

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_{&omega;^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;,&kappa;)}, for Mostowski-Rabin indices (ıκ). We prove that the D_{&omega;^n}(Σ^1_1)-complete tree languages L_n are Wadge reducible to the game tree language W_{(&inodot;,&kappa;)} for κ−ı⩾ 2. In particular these languages W_{(&inodot;,&kappa;)} are not in any class D_{&alpha;}(Σ^1_1) for α<ω^{&omega;}.

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

DOI: 10.3233/FI-2009-151

Journal: Fundamenta Informaticae, vol. 95, no. 2-3, pp. 287-303, 2009