nach oben

Journal of Logic, Language and Information

Erschienen in:

01.09.2015

Dependence Logic with a Majority Quantifier

verfasst von: Arnaud Durand, Johannes Ebbing, Juha Kontinen, Heribert Vollmer

Erschienen in: Journal of Logic, Language and Information | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the extension of dependence logic \(\mathcal {D}\) by a majority quantifier \(\mathsf{M}\) over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, \(\mathcal {D}(\mathsf{M})\) captures the complexity class counting hierarchy. We also obtain characterizations of the individual levels of the counting hierarchy by fragments of \(\mathcal {D}(\mathsf{M})\).

Vorheriger Artikel Preference Change

Nächster Artikel A Logic for Trial and Error Classifiers

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abramsky, S., & Väänänen, J. (2009). From IF to BI. Synthese, 167(2), 207–230.CrossRef

Allender, E. (1999). The permanent requires large uniform threshold circuits. Chicago Journal of Theoretical Computer Science, 7, 19. (electronic).

Andersson, A. (2002). On second-order generalized quantifiers and finite structures. Annals of Pure and Applied Logic, 115(1–3), 1–32.CrossRef

Burtschick, H.-J., & Vollmer, H. (1998). Lindström quantifiers and leaf language definability. International Journal of Foundations of Computer Science, 9(3), 277–294.CrossRef

Durand, A., Ebbing, J., Kontinen, J., & Vollmer, H. (2011). Dependence logic with a majority quantifier. In S. Chakraborty & A. Kumar (Eds.), IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) (Vol. 13, pp. 252–263)., Leibniz International Proceedings in Informatics (LIPIcs) Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Ebbing, J. (2014). Complexity and expressivity of dependence logic extensions. PhD thesis, Leibniz Universität Hannover.

Ebbinghaus, H.-D., & Flum, J. (1999). Finite model theory perspectives in mathematical logic (2nd ed.). Heidelberg: Springer.CrossRef

Engström, F. (2012). Generalized quantifiers in dependence logic. Journal of Logic, Language and Information, 21(3), 299–324.CrossRef

Engström, F., & Kontinen, J. (2013). Characterizing quantifier extensions of dependence logic. The Journal of Symbolic Logic, 78(1), 307–316.CrossRef

Galliani, P. (2012). Inclusion and exclusion dependencies in team semantics—On some logics of imperfect information. Annals of Pure and Applied Logic, 163(1), 68–84.CrossRef

Grädel, E., & Väänänen, J. A. (2013). Dependence and independence. Studia Logica, 101(2), 399–410.CrossRef

Henkin, L. (1961). Some remarks on infinitely long formulas. In Infinitistic Methods (Proceedings of the Symposium of Foundations of Mathematics, Warsaw, 1959) (pp. 167–183). Pergamon, Oxford.

Hintikka, J., & Sandu, G. (1989). Informational independence as a semantical phenomenon. In Logic, methodology and philosophy of science, VIII (Moscow, 1987), Vol 126 of Studies in Logic and the Foundations of Mathematics (pp. 571–589). North-Holland, Amsterdam.

Kontinen, J. (2006). The hierarchy theorem for second order generalized quantifiers. The Journal of Symbolic Logic, 71(1), 188–202.CrossRef

Kontinen, J. (2009). A logical characterization of the counting hierarchy. ACM Transactions on Computational Logic (TOCL), 10(1), 7.CrossRef

Kontinen, J. (2010). Definability of second order generalized quantifiers. Archive for Mathematical Logic, 49(3), 379–398.CrossRef

Kontinen, J., & Niemistö, H. (2011). Extensions of MSO and the monadic counting hierarchy. Information and Computation, 209(1), 1–19.CrossRef

Kontinen, J., & Szymanik, J. (2014). A characterization of definability of second-order generalized quantifiers with applications to non-definability. Journal of Computer and System Sciences, 80(6), 1152–1162.CrossRef

Kontinen, J., & Väänänen, J. (2009). On definability in dependence logic. Journal of Logic, Language and Information, 18(3), 317–332.CrossRef

Lindström, P. (1966). First order predicate logic with generalized quantifiers. Theoria, 32, 186–195.

Lohmann, P., & Vollmer, H. (2013). Complexity results for modal dependence logic. Studia Logica, 101(2), 343–366.CrossRef

Sevenster, M. (2009). Model-theoretic and computational properties of modal dependence logic. Journal of Logic and Computation, 19(6), 1157–1173.CrossRef

Toda, S. (1991). PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5), 865–877.CrossRef

Toda, S., & Watanabe, O. (1992). Polynomial time 1-turing reductions from #PH to #P. Theoretical Computer Science, 100(1), 205–221.CrossRef

Torán, J. (1991). Complexity classes defined by counting quantifiers. Journal of the ACM, 38(3), 753–774.CrossRef

Väänänen, J. (1999). Generalized quantifiers, an introduction. In Generalized quantifiers and computation (Aix-en-Provence, 1997), Vol 1754 of Lecture Notes in Computer Science (pp. 1–17). Berlin: Springer.

Väänänen, J. (2007). Dependence logic: A new approach to independence friendly logic, volume 70 of London mathematical society student texts. Cambridge: Cambridge University Press.CrossRef

Väänänen, J. (2008). Modal dependence logic. In K. Apt & R. van Rooij (Eds.), New perspectives on games and interaction, volume 5 of texts in logic and games (pp. 237–254). Amsterdam: Amsterdam University Press.

Vollmer, H. (1999). Introduction to circuit complexity—-A uniform approach. In W. Brauer, G. Rozenberg & A. Salomaa (Eds.), Texts in Theoretical Computer Science—An EATCS Series. Berlin, Heidelberg: Springer.

Wagner, K. (1986). The complexity of combinatorial problems with succint input representation. Acta Informatica, 23, 325–356.CrossRef

Yang, F. (2013). Expressing second-order sentences in intuitionistic dependence logic. Studia Logica, 101(2), 323–342.CrossRef

Titel: Dependence Logic with a Majority Quantifier
verfasst von: Arnaud Durand
Johannes Ebbing
Juha Kontinen
Heribert Vollmer
Publikationsdatum: 01.09.2015
Verlag: Springer Netherlands
Erschienen in: Journal of Logic, Language and Information / Ausgabe 3/2015
Print ISSN: 0925-8531
Elektronische ISSN: 1572-9583
DOI: https://doi.org/10.1007/s10849-015-9218-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

A Logic for Trial and Error Classifiers

Comparison Across Domains in Delineation Semantics

Weak Negation in Inquisitive Semantics

Preference Change

Premium Partner