Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Logic, Language and Information
Published in: Journal of Logic, Language and Information 3/2015

01-09-2015

Dependence Logic with a Majority Quantifier

Authors: Arnaud Durand, Johannes Ebbing, Juha Kontinen, Heribert Vollmer

Published in: Journal of Logic, Language and Information | Issue 3/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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})\).
previous article Preference Change
next article A Logic for Trial and Error Classifiers

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
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
Metadata
Title
Dependence Logic with a Majority Quantifier
Authors
Arnaud Durand
Johannes Ebbing
Juha Kontinen
Heribert Vollmer
Publication date
01-09-2015
Publisher
Springer Netherlands
Published in
Journal of Logic, Language and Information / Issue 3/2015
Print ISSN: 0925-8531
Electronic ISSN: 1572-9583
DOI
https://doi.org/10.1007/s10849-015-9218-3

Other articles of this Issue 3/2015

Journal of Logic, Language and Information 3/2015 Go to the issue

OriginalPaper

A Logic for Trial and Error Classifiers

OriginalPaper

Weak Negation in Inquisitive Semantics

OriginalPaper

Comparison Across Domains in Delineation Semantics

OriginalPaper

Preference Change

Premium Partner

    Image Credits