Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Trees

• Autorzy: Bárány V. , Kaiser Ł. , Rabinovich A.
• Języki publikacji: EN

Abstrakty

EN

We study an extension of monadic second-order logic of order with the uncountability quantifier "there exist uncountably many sets". We prove that, over the class of finitely branching trees, this extension is equally expressive to plain monadic second-order logic of order. Additionally we find that the continuum hypothesis holds for classes of sets definable in monadic second-order logic over finitely branching trees, which is notable for not all of these classes are analytic. Our approach is based on Shelah’s composition method and uses basic results from descriptive set theory. The elimination result is constructive, yielding a decision procedure for the extended logic.

Słowa kluczowe

EN

infinite trees; monadic 2nd-order logic; cardinality quantifiers; Cantor topology

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 100, nr 1/4
• Strony: 1--17
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Bárány V.

autor

Kaiser Ł.

autor

Rabinovich A.

• RWTH Aachen, Mathematische Grundlagen der Informatik, Germany,

Bibliografia

• [1] Arnold, A., Duparc, J., Murlak, F., Niwiński, D.: On the topological complexity of tree languages. In Logic and Automata: History and Perspectives, volume 2 of Texts in Logic and Games, pages 9-29. Amsterdam University Press, 2007.
• [2] Baudisch, A., Seese, D., Tuschik, H. P., Weese, M.: Decidability and Generalized Quantifiers. Akademie- Verlag Berlin, 1980.
• [3] Bárány, V., Kaiser, Ł., Rabinovich, A.: Cardinality Quantifiers in MLO over Trees. In Proc. 18th EACSL Annual Conference on Computer Science Logic, CSL'09, (E. Gr¨adel and R. Kahle, Eds.), vol. 5771 of LNCS, pp. 117-132. Springer, 2009.
• [4] Bárány, V., Kaiser, Ł., Rabinovich, A.: Expressing Cardinality Quantifiers in Monadic Second-Order Logic over Chains. to appear in J. Symb. Logic.
• [5] Blumensath, A.: Automatic structures. Diploma thesis, RWTH Aachen, 1999.
• [6] Bojańczyk, M., Niwiński, D., Rabinovich, A., Radziwończyk-Syta, A., Skrzypczak, M.: On the Borel Complexity of MSO Definable Sets of Branches. Fundamenta Informaticae, 98(4):337-349, 2010.
• [7] Büchi, J. R.: Weak second-order arithmetic and finite automata. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 6:66-92, 1960.
• [8] Colcombet, Th., Löding, Ch.: Transforming structures by set interpretations. Logical Methods in Computer Science, 3(2:4):1-36, 2007.
• [9] Elgot, C. C.: Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Society, 98:21-51, 1961.
• [10] Gurevich, Y.: Monadic second-order theories. In Jon Barwise and Solomon Feferman, editors, Model-Theoretical Logics, pages 479-506. Springer, 1985.
• [11] Hintikka, J.: Distributive normal forms in the calculus of predicates. Acta Philosophica Fennica 6 (1953).
• [12] Kechris, A. S.: Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, 1995.
• [13] Kuske, D., Lohrey,M.: First-order and counting theories of omega-automatic structures. Journal of SymbolicLogic, 73:129-150, 2008.
• [14] Moschovakis, Y. N.: Descriptive Set Theory, volume 100 of Studies in Logic and the Foundations of Mathematics.North-Holland Publishing Company, 1980.
• [15] Niwiński, D.: On the cardinality of sets of infinite trees recognizable by finite automata. In Proceedings of Mathematical Foundations of Computer Science, MFCS'91, volume 520 of LNCS, pages 367-376. Springer, 1991.
• [16] Niwiński, D., Walukiewicz, I.: A gap property of deterministic tree languages. Theoretical Computer Science, 1(303):215-231, 2003.
• [17] Rabin, M. O.: Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969.
• [18] Rubin, S.: Automata Presenting Structures: A Survey of the Finite String Case. Bulletin of Symbolic Logic, 14(2):169-209, 2008.
• [19] Shelah, S.: The monadic theory of order. Annals of Mathematics, 102:379-419, 1975.
• [20] Skurczyński J.: The Borel hierarchy is infinite in the class of regular sets of trees. Theoretical Computer Science 112(2): 413-418, 1993.
• [21] Thomas, W.: Ehrenfeucht games, the composition method, and the monadic theory of ordinal words. In Structures in Logic and Computer Science, volume 1261 of Lecture Notes in Computer Science, pages 118-143. Springer, 1997.
• [22] Thomas,W., Lescow, H.: Logical specifications of infinite computations. In J.W. de Bakker,W. P. de Roever, and G. Rozenberg, editors, REX School/Symposium, volume 803 of LNCS, pages 583-621. Springer, 1993.
• [23] Trakhtenbrot, B. A.: Finite automata and the logic of monadic predicates. Dokl. Akad. Nauk SSSR, 140:326-329, 1961.
• [24] Trakhtenbrot, B. A.: Finite automata and the logic of one-place predicates. Sibirian Mathematical Journal,13:103-131, 1962. (in Russian).