An upper bound on the complexity of recognizable tree languages

¹ Equipe de Logique Mathématique, Institut de Mathématiques de Jussieu – Paris Rive Gauche, CNRS et Université Paris Diderot Paris 7, Bâtiment Sophie Germain Case 7012, 75205 Paris cedex 13, France.
finkel@math.univ-paris-diderot.fr
² Projet Analyse FonctionnelleInstitut de Mathématiques de Jussieu – Paris Rive Gauche Université Pierre et Marie Curie Paris 6 Couloir 16-26, 4ème étage, Case 247, 4, place Jussieu, 75252 Paris cedex 05, France.
dominique.lecomte@upmc.fr
³ Université de Picardie,I.U.T. de l’Oise, site de Creil 13, allée de la faïencerie, 60107 Creil, France
⁴ UMR CNRS 6134, Faculté des Sciences, Université de Corse, Quartier Grossetti BP 52, 20250 Corte, France.
simonnet@univ-corse.fr

Received: 11 September 2014
Accepted: 9 March 2015

Abstract

The third author noticed in his 1992 Ph.D. thesis [P. Simonnet, Automates et théorie descriptive (1992).] that every regular tree language of infinite trees is in a class $a\mathrm{\left(}{\mathit{D}}_{\mathit{n}}\mathrm{\right(}{{\Sigma }}_{\mathrm{2}}^{\mathrm{0}}\mathrm{\left)}\mathrm{\right)}$ for some natural number n ≥ 1, where $a_{}^{}$ is the game quantifier. We first give a detailed exposition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space 2^ω into the class ∆₂¹, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ∆₂¹.