On Recognizable Tree Languages Beyond the Borel Hierarchy

• Autorzy: Finkel O. , Simonnet P.
• Języki publikacji: EN

Abstrakty

EN

We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer n ≥1, there is a D_{&omega n;}(Σ¹) -complete tree language L_n accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree languages W_(l,k), for Mostowski-Rabin indices (, k). We prove that the D_{&omega n;}(Σ¹) -complete tree languages Ln are Wadge reducible to the game tree languageW_(l,k) for k-l≥2. In particular these languagesW_(l,k) are not in any class D_{&omega n;}(Σ¹) for α<ω^ω

Słowa kluczowe

EN

infinite trees; tree automaton; regular tree languages; Cantor topology; topological complexity; Borel hierarchy; difference hierarchy of analytic sets; complete sets; unambiguous tree automaton; game tree language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 95, nr 2/3
• Strony: 287--303
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Finkel O.

autor

Simonnet P.

• Systemes physiques pour l'environnement, Faculté des Sciences, Université de Corse, Quartier Grossetti BP52 20250, Corte, France,

Bibliografia

• [1] A. Arnold, J. Duparc, F. Murlak, and D. Niwinski. On the topological complexity of tree languages. In J. Flum, E. Gr¨adel, and T. Wilke, editors, Logic and Automata: History and Perspectives, pages 9-28. Amsterdam University Press, 2007.
• [2] A. Arnold and D. Niwinski. Continuous separation of game languages. Fundamenta Informaticae, 81(1-3):19-28, 2008.
• [3] B. Cagnard and P. Simonnet. Baire and automata. Discrete Mathematics and Theoretical Computer Science, 9(2):255-296, 2007.
• [4] O. Finkel and P. Simonnet. Topology and ambiguity in omega context free languages. Bulletin of the Belgian Mathematical Society, 10(5):707-722, 2003.
• [5] E. Gr¨adel, W. Thomas, and W. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002.
• [6] A. Kanamori. The Higher Infinite. Springer-Verlag, 1997.
• [7] A. S. Kechris. Classical descriptive set theory. Springer-Verlag, New York, 1995.
• [8] H. Lescow and W. Thomas. Logical specifications of infinite computations. In J. W. de Bakker, Willem P. de Roever, and Grzegorz Rozenberg, editors, A Decade of Concurrency, volume 803 of Lecture Notes in Computer Science, pages 583-621. Springer, 1994.
• [9] Y. N. Moschovakis. Descriptive set theory. North-Holland Publishing Co., Amsterdam, 1980.
• [10] F. Murlak. On deciding topological classes of deterministic tree languages. In Proceedings of CSL 2005, 14th Annual Conference of the EACSL, volume 3634 of Lecture Notes in Computer Science, pages 428-441. Springer, 2005.
• [11] F. Murlak. The Wadge hierarchy of deterministic tree languages. Logical Methods in Computer Science, 4(4, paper 15), 2008.
• [12] D. Niwinski. An example of non Borel set of infinite trees recognizable by a Rabin automaton. 1985. In Polish, manuscript.
• [13] D. Niwinski. 2009. Personal communication.
• [14] D. Niwinski and I. Walukiewicz. A gap property of deterministic tree languages. Theoretical Computer Science, 1(303):215-231, 2003.
• [15] D. Perrin and J.-E. Pin. Infinite words, automata, semigroups, logic and games, volume 141 of Pure and Applied Mathematics. Elsevier, 2004.
• [16] M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969.
• [17] P. Simonnet. Automates et théorie descriptive. PhD thesis, Université Paris VII, 1992.
• [18] J. Skurczynski. The Borel hierarchy is infinite in the class of regular sets of trees. Theoretical Computer Science, 112(2):413-418, 1993.
• [19] L. Staiger. Hierarchies of recursive !-languages. Elektronische Informationsverarbeitung und Kybernetik, 22(5-6):219-241, 1986.
• [20] L. Staiger. !-languages. In Handbook of formal languages, Vol. 3, pages 339-387. Springer, Berlin, 1997.
• [21] J.R. Steel. Determinacy in the mitchell models. Annals of Mathematical Logic, 22:109-125, 1982.
• [22] W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, Formal models and semantics, pages 135-191. Elsevier, 1990.
• [23] W. Thomas. Languages, automata, and logic. In Handbook of formal languages, Vol. 3, pages 389-455. Springer, Berlin, 1997.