The Topological Complexity of MSO+U and Related Automata Models

• Autorzy: Hummel S. , Skrzypczak M.
• Języki publikacji: EN

Abstrakty

EN

This work shows that for each i ∈ω there exists aΣ -hard ωword language definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO+U). This quantifier was introduced by Bojańczyk to express some asymptotic properties. Since it is not hard to see that each language expressible in MSO+U is projective, our finding solves the topological complexity of MSO+U. The result can immediately be transferred from !-words to infinite labelled trees. As a consequence of the topological hardness we note that no alternating automaton with a Borel acceptance condition — or even with an acceptance condition of a bounded projective complexity — can capture all of MSO+U. The same holds for deterministic and nondeterministic automata since they are special cases of alternating ones. We also give exact topological complexities of related classes of languages recognized by nondeterministic ωB-, ωS- and ωBS-automata studied by Bojańczyk and Colcombet. Furthermore, we show that corresponding alternating automata have higher topological complexity than nondeterministic ones— they inhabit all finite levels of the Borel hierarchy. The paper is an extended journal version of [8]. The main theorem of that article is strengthened here.

Słowa kluczowe

EN

MSO+U; omegaBS-automata; topological complexity; projective hierarchy; Borel hierarchy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 119, nr 1
• Strony: 87--111
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Hummel S.

autor

Skrzypczak M.

• Institute of Informatics, University of Warsaw, Banacha 2, Poland,

Bibliografia

• [1] Bojańczyk, M.: A Bounding Quantifier, CSL, 2004.
• [2] Bojańczyk, M.: Beyond !-Regular Languages, STACS, 2010.
• [3] Bojańczyk, M.: Weak MSO with the Unbounding Quantifier, Theory Comput. Syst., 48(3), 2011, 554-576.
• [4] Bojańczyk, M., Colcombet, T.: Bounds in !-Regularity, LICS, 2006.
• [5] Bojańczyk, M., Toruńczyk, S.: Deterministic Automata and Extensions of Weak MSO, FSTTCS, 2009.
• [6] Büchi, J. R.: On a Decision Method in Restricted Second-Order Arithmetic, Proc. 1960 Int. Congr. for Logic, Methodology and Philosophy of Science, 1962.
• [7] Cabessa, J., Duparc, J., Facchini, A., Murlak, F.: TheWadge Hierarchy of Max-Regular Languages, FSTTCS, 2009.
• [8] Hummel, S., Skrzypczak, M., Toruńczyk, S.: On the Topological Complexity of MSO+U and Related Automata Models, MFCS, 2010.
• [9] Kechris, A.: Classical descriptive set theory, Springer-Verlag, New York, 1995.
• [10] Kuratowski, K.: Topology. Vol. I, Academic Press, New York, 1966.
• [11] McNaughton, R.: Testing and Generating Infinite Sequences by a Finite Automaton, Information and Control, 9(5), 1966, 521-530.
• [12] Niwiński, D., Walukiewicz, I.: A gap property of deterministic tree languages, Theor. Comput. Sci., 1(303), 2003, 215-231.
• [13] Rabin, M. O.: Decidability of second-order theories and automata on infinite trees, Bull. Amer. Math. Soc., 74, 1968, 1025-1029.
• [14] Safra, S.: On the Complexity of omega-Automata, FOCS, 1988.
• [15] Skurczyński, J.: The Borel hierarchy is infinite in the class of regular sets of trees, Theoretical Computer Science, 112(2), 1993, 413-418.
• [16] Srivastava, S. M.: A Course on Borel Sets, vol. 180 of Graduate Texts in Mathematics, Springer-Verlag, 1998.
• [17] Thomas,W.: Languages, Automata and Logics, Technical Report 9607, Institut für Informatik und Praktische Mathematik, Christian-Albsechts-Universität, Kiel, Germany, 1996.
• [18] Thomas, W., Lescow, H.: Logical Specifications of Infinite Computations, REX School/Symposium, 1993.
• [19] Wadge, W.: Reducibility and determinateness in the Baire space, Ph.D. Thesis, University of California, Berkeley, 1983.