AN UPPER BOUND ON THE COMPLEXITY OF RECOGNIZABLE TREE LANGUAGES

作者：Finkel Olivier^*; Lecomte Dominique; Simonnet Pierre

来源：RAIRO - Theoretical Informatics and Applications, 2015, 49(2): 121-137.

DOI：10.1051/ita/2015002

• Infinite trees
• tree automaton
• regular tree language
• Cantor topology
• topological complexity
• Borel hierarchy
• game quantifier
• Wadge classes
• Wadge degrees
• universal sets
• provably-Delta(1)(2)

The third author noticed in his 1992 Ph.D. thesis [P. Simonnet, Automates et theorie descriptive (1992).] that every regular tree language of infinite trees is in a class (D-n(Sigma(0)(2))) for some natural number n >= 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(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 Delta(1)(2).

• 出版日期2015-6