Continuous Separation of Game Languages

• Autorzy: Arnold A. , Niwiński D.
• Języki publikacji: EN

Abstrakty

EN

We show that a family of tree languages W(i,k) , previously used by J. Bradfield, and by the first author to show the strictness of the Rabin-Mostowski index hierarchy of alternating tree automata, forms a hierarchy w.r.t. the Wadge reducibility. That is, [formula] if and only if the index [...] is above (i,k) . This is one of the few separation results known so far, concerning the topological complexity of non-deterministically recognizable tree languages, and one of the few results about finite-state recognizable non-Borel sets of trees.

Słowa kluczowe

EN

wadge reducibility; infinite trees; automata; Rabin-Mostowski inex

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 1-3
• Strony: 19--28
• Opis fizyczny: bibliogr. 23 poz.

Twórcy

autor

Arnold A.

autor

Niwiński D.

• LaBRI, Universite of Bordeaux I, France,

Bibliografia

• [1] Addison, J.W., Tarski's theory of definability: common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic. Annals of Pure and Applied Logic 126 (2004), 77-92.
• [2] Arnold, A., The μ-calculus alternation-depth hierarchy is strict on binary trees. RAIRO-Theoretical Informatics and Applications 33 (1999), 329-339.
• [3] Arnold, A., and Niwiński, D., Rudiments of μ-Calculus. Elsevier Science, Studies in Logic and the Foundations of Mathematics, 146, North-Holland, Amsterdam, 2001.
• [4] Bradfield, J.C., The modal mu-calculus alternation hierarchy is strict. Theoret. Comput. Sci. 195 (1997), 133-153.
• [5] Bradfield, J.C., Simplifying the modal mu-calculus alternation hierarchy. In: Proc. STACS'98, Lect. Notes Comput. Sci. 1373 (1998), 39-49.
• [6] Emerson, E.A., and C. S. Jutla, C. S., Tree automata, mu-calculus and determinacy. In: Proceedings 32th Annual IEEE Symp. on Foundations of Comput. Sci. (1991), 368-377.
• [7] Grädel, E., Thomas, W., and Wilke, T., Editors, Automata, Logics, and Infinite Games. A Guide to Current Research, Lect. Notes Comput. Sci. 1500, Springer-Verlag, 2002.
• [8] P. G. Hinman, P. G., Recursion-Theoretic Hierarchies. Springer-Verlag, Heidelberg, New York, 1978.
• [9] Kechris, A.S., Classical descriptive set theory. Springer-Verlag, New York, 1995.
• [10] Landweber, L.H., Decision problems for !-automata. Math. Systems Theory 3 (1969), 376-384.
• [11] Lenzi, G., A hierarchy theorem for the mu-calculus. In: F. M. auf der Heide and B. Monien, editors, Proc. ICALP '96, Lect. Notes Comput. Sci. 1099 (1996), 87-109.
• [12] Mostowski, A. W., Games with forbidden positions. Technical Report 78, Instytut Matematyki, University of Gdansk, 1991.
• [13] Muller, D.E., Schupp, P.E., Simulating alternating tree automata by nondeterministic automata: new results and new proofs of the theorems of Rabin,McNaughton and Safra. Theoret. Comput. Sci. 141 (1995), 69-107.
• [14] Murlak, F., The Wadge Hierarchy of Deterministic Tree Languages. In: Proc. ICALP 2006, Lect. Notes Comput. Sci. 4052 (2006), 408-419.
• [15] Niwiński, D., On fixed point clones. In: ICALP'86, Lect. Notes Comput. Sci. 226, Springer-Verlag, 1986, 464-473.
• [16] Niwiński, D., and Walukiewicz, I., A gap property of deterministic tree languages. Theoret. Comput. Sci. 303 (2003), 215-231.
• [17] Perrin, D., and Pin, J.-E., Infinite Words. Automata, Semigroups, Logic and Games. Pure and Applied Mathematics Vol 141, Elsevier, 2004.
• [18] Rabin, M.O., Decidability of second-order theories and automata on infinite trees. Trans. Amer. Soc., 141:1-35, 1969.
• [19] Rabin, M.O., Weakly definable relations and special automata. In: Mathematical Logic and Foundations of Set Theory, Y. Bar-Hillel ed., 1970, 1-23.
• [20] Skurczyński, J., The Borel hierarchy is infinite in the class of regular sets of trees. Theoret. Comput. Sci. 112 (1993), 413-418.
• [21] Thomas,W., Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume 3, Springer-Verlag, 1997, pp. 389-455.
• [22] Wadge, W., Reducibility and determinateness in the Baire space. Ph.D. Thesis, University of California, Berkeley, 1983.
• [23] Wagner, K., On !-regular sets. Inform. and Control 43 (1979), 123-177.