On the Borel Complexity of MSO Definable Sets of Branches

• Autorzy: Bojańczyk M. , Niwiński D. , Rabinovich A. , Radziwończyk–Syta A. , Skrzypczak M.
• Języki publikacji: EN

Abstrakty

EN

An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.

Słowa kluczowe

EN

monadic 2nd-order logic; infinite words; trees; Borel hierarchy; automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 98, nr 4
• Strony: 337--349
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Bojańczyk M.

autor

Niwiński D.

autor

Rabinovich A.

autor

Radziwończyk–Syta A.

autor

Skrzypczak M.

• Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland,

Bibliografia

• [1] Báárány, V., and Kaiser, Ł., and Rabinovich, A., Cardinality quantifiers in MLO over trees. In Proc. 18th EACSL Annual Conference on Computer Science Logic, Vol. 5771 of LNCS, pages 117-131, 2009.
• [2] Büchi, J.R., On a decision method in restricted second order arithmetic. In Logic, Methodology, and Philosophy of Science, pp. 1-11, Stanford Univ. Press, 1960.
• [3] Ebbinghaus, H.D., and Flum, J., and Thomas,W., Mathematical Logic. Springer, 1984.
• [4] Emerson, E.A., and Jutla, C.S., The complexity of tree automata and logics of programs. In Proc. 29th Foundations of Computer Science, pp. 368-377, 1988.
• [5] Fratani, S., Automates `a piles de piles. . . de piles. PhD thesis, Universit´e Bordeaux I, 2005 (in French).
• [6] Kechris, A.S., Classical Descriptive Set Theory. Springer, 1995.
• [7] Landweber, L.H. Decision problems for ω-automata. Math. Systems Theory 3 (1969) 376-384.
• [8] Lifsches, S., and Shelah, S., Uniformization and Skolem functions in the class of trees. J.Symbolic Logic, Vol. 63(1) (1998), 103-127.
• [9] McNaughton, R., Testing and generating infinite sequences by finite automaton. Information and Control 9 (1966), 521-530.
• [10] Niwiński, D., and Walukiewicz, I., A gap property of deterministic tree languages. Theoret. Comput. Sci. 303 (2003), 215-231.
• [11] Rabin, M.O., Decidability of second-order theories and automata on infinite trees. Trans. Amer. Soc., 141:1-35, 1969.
• [12] Safra, S., On the complexity of ω-automata. In Proc. 29th Foundations of Computer Science, pp. 319-327, 1988.
• [13] J. Skurczyński. The Borel hierarchy is infinite in the class of regular sets of trees. Theoret. Comput. Sci. 112 (1993) 413-418.
• [14] Thomas, W., Automata on infinite objects. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science , volume B, pages 133-191. Elsevier Science Pub., 1990.
• [15] 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.