An upper bound on the complexity of recognizable tree languages

Finkel, Olivier; Lecomte, Dominique; Simonnet, Pierre

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

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$.

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

A. Arnold, J. Duparc, F. Murlak and D. Niwinski, On the topological complexity of tree languages. In Logic and Automata: History and Perspectives, edited by J. Flum, E. Grädel and T. Wilke. Amsterdam University Press (2007) 9–28. | MR | Zbl

A. Arnold and D. Niwinski, Continuous separation of game languages. Fundamenta Informaticae 81 (2008) 19–28. | MR | Zbl

M. Bojanczyk and T. Place, Regular languages of infinite trees that are boolean combinations of open sets. In Proc. of Automata, Languages, and Programming – 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Part II. Edited by A. Czumaj, K. Mehlhorn, A.M. Pitts and R. Wattenhofer. Vol. 7392 of Lect. Notes Comput. Sci. Springer (2012) 104–115. | MR

J.C. Bradfield, Fixpoints, games and the difference hierarchy. RAIRO: ITA 37 (2003) 1–15. | Numdam | MR | Zbl

J.C. Bradfield, J. Duparc and S. Quickert, Transfinite extension of the mu-calculus. In Proc. of Computer Science Logic, 19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005. Edited by C.-H. Luke Ong. Vol. 3634 of Lect. Notes Comput. Sci. Springer (2005) 384–396. | MR | Zbl

B. Cagnard and P. Simonnet, Baire and automata. Discrete Math. Theor. Comput. Sci. 9 (2007) 255–296. | MR | Zbl

J. Duparc, Wadge hierarchy and Veblen hierarchy: Part 1: Borel sets of finite rank. J. Symbolic Logic 66 (2001) 56–86. | DOI | MR | Zbl

A. Facchini and H. Michalewski, Deciding the Borel complexity of regular tree languages. In Proc. of Language, Life, Limits – 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Edited by A. Beckmann, E. Csuhaj-Varjú and K. Meer. Vol. 8493 of Lect. Notes Comput. Sci. Springer (2014) 163–172. | MR

O. Finkel, The determinacy of context-free games. J. Symbolic Logic 78 (2013) 1115–1134. | DOI | MR | Zbl

O. Finkel, Infinite games specified by $2$-tape automata (2013). Preprint, available from . | arXiv | MR

O. Finkel and P. Simonnet, On recognizable tree languages beyond the Borel hierarchy. Fundamenta Informaticae 95 (2009) 287–303. | DOI | MR | Zbl

T. Gogacz, H. Michalewski, M. Mio and M. Skrzypczak, Measure properties of game tree languages. In Proc. of Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014, Part I. Edited by E. Csuhaj-Varjú, M. Dietzfelbinger and Z. Ésik. Vol. 8634 of Lect. Notes Comput. Sci. Springer (2014) 303–314. | MR

Y. Gurevich and L. Harrington, Trees, automata, and games. In Proc. of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. Edited by H.R. Lewis, B.B. Simons, W.A. Burkhard, and L.H. Landweber. ACM (1982) 60–65.

E. Grädel, W. Thomas and W. Wilke. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Vol. 2500 of Lect. Notes Comput. Sci. Springer (2002). | MR | Zbl

G. Hjorth, B. Khoussainov, A. Montalbán and A. Nies, From automatic structures to Borel structures. In Proc. of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24-27 June 2008, Pittsburgh, PA, USA. IEEE Computer Society (2008) 431–441.

S. Hummel, Unambiguous tree languages are topologically harder than deterministic ones. In Proc. of Third International Symposium on Games, Automata Logics and Formal Verification, GandALF 2012, Napoli, Italy, September 6-8, 2012. Edited by M. Faella and A. Murano, Vol. 96 of EPTCS (2012) 247–260.

T. Jech, Set theory, 3rd edition. Springer (2002). | MR | Zbl

A. Kanamori, The Higher Infinite. Springer-Verlag (1997). | MR | Zbl

A.S. Kechris, Classical descriptive set theory. Springer-Verlag, New York (1995). | MR | Zbl

A. Louveau and J. Saint-Raymond, The strength of Borel Wadge determinacy. In Cabal Seminar 81–85. Vol. 1333 of Lect. Note Math. Springer (1988) 1–30. | MR | Zbl

H. Lescow and W. Thomas, Logical specifications of infinite computations. In A Decade of Concurrency. Edited by J.W. de Bakker, W.P. de Roever and Grzegorz Rozenberg. Vol. 803 of Lect. Notes Comput. Sci. Springer (1994) 583–621. | MR

H. Michalewski and D. Niwinski, On topological completeness of regular tree languages. In Logic and Program Semantics – Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday. Edited by R.L. Constable and A. Silva. Vol. 7230 of Lect. Notes Comput. Sci. Springer (2012) 165–179. | MR

Y.N. Moschovakis, Descriptive set theory, vol. 155 of Math. Surveys Monographs. American Mathematical Society, Providence, RI, 2nd edition (2009). | MR | Zbl

F. Murlak, The Wadge hierarchy of deterministic tree languages. Log. Methods Comput. Sci. 4 (2008) 15. | DOI | MR | Zbl

D. Niwinski, An example of non Borel set of infinite trees recognizable by a Rabin automaton (1985). In Polish, manuscript.

D. Niwinski and I. Walukiewicz, A gap property of deterministic tree languages. Theor. Comput. Sci. 1 (2003) 215–231. | DOI | MR | Zbl

D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games, vol. 141 of Pure Appl. Math. Elsevier (2004). | Zbl

M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141 (1969) 1–35. | MR | Zbl

P. Simonnet, Automates et théorie descriptive. Ph.D. thesis, Université Paris VII (1992).

J. Skurczynski, The Borel hierarchy is infinite in the class of regular sets of trees. Theor. Comput. Sci. 112 (1993) 413–418. | DOI | MR | Zbl

J. Saint Raymond, Quasi-bounded trees and analytic inductions. Fundamenta Mathematicae 191 (2006) 175–185. | DOI | MR | Zbl

L. Staiger, $\omega$-languages. In vol. 3 of Handb. Formal Languages. Springer, Berlin (1997) 339–387. | MR

W. Thomas, Automata on infinite objects. Formal models and semantics. Edited by J. van Leeuwen, vol. B. Handb. Theoret. Comput. Sci. Elsevier (1990) 135–191. | MR | Zbl

W. Thomas, Languages, automata, and logic. In vol. 3 of Handb. Formal Languages. Springer, Berlin (1997) 389–455. | MR

W. Wadge, Reducibility and determinateness in the Baire space. Ph.D. thesis, University of California, Berkeley (1983). | MR