An Upper Bound on the Complexity of Recognizable Tree Languages

Olivier Finkel (1, 2) , Dominique Lecomte (2) , Pierre Simonnet (3)

1 ELM - Équipe de Logique Mathématique
2 IMJ - Institut de Mathématiques de Jussieu
3 SPE - Sciences pour l'environnement

The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $\Game (D_n({\bf\Sigma}^0_2))$ for some natural number $n\geq 1$, where $\Game$ 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 ${\bf\Delta}^1_2$, 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 ${\bf\Delta}^1_2$.

Keywords: provably-${\it\Delta}^1_2$; universal sets; Wadge degrees; Wadge classes; game quantifier; infinite trees; tree automaton; topological complexity; regular tree language; Cantor topology; Borel hierarchy

Domains: Computation and Language [cs.CL]; Logic [math.LO]; General Topology [math.GN]

Olivier Finkel, Dominique Lecomte, Pierre Simonnet. An Upper Bound on the Complexity of Recognizable Tree Languages. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), 2015, 49 (2), pp.121-137. ⟨hal-01128609⟩