An Upper Bound on the Complexity of Recognizable Tree Languages

Olivier Finkel, Dominique Lecomte, Pierre Simonnet

The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $⅁(D\_n({\mathbf{\Sigma }}^0\_2))$ for some natural number $n\geq…