Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button


Fundamenta Informaticae

Tytuł artykułu

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. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
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.
autor Bojańczyk, M.
autor Niwiński, D.
autor Rabinovich, A.
autor Radziwończyk–Syta, A.
autor Skrzypczak, M.
[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.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-BUS8-0010-0018