An upper bound on the complexity of recognizable tree languages

Finkel, Olivier¹  ; Lecomte, Dominique^2, 3 ; Simonnet, Pierre⁴

¹ 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.
² 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.
³ 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.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 2, pp. 121-137

Résumé

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 $⅁\left(D_n\left({\Sigma }_2^0\right)\right)$ for some natural number $n\ge 1$, where $⅁$ 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^{\omega }$ into the class ${\Delta }_2^1$, 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 ${\Delta }_2^1$.

Détail

DOI : 10.1051/ita/2015002

Classification : 03E15, 03B70, 54H05, 68Q15, 68Q45
Keywords: Infinite trees, tree automaton, regular tree language, Cantor topology, topological complexity, Borel hierarchy, game quantifier, Wadge classes, Wadge degrees, universal sets, provably-Δ¹₂