Document Open Access Logo

Dependence logic with a majority quantifier

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2011.252.pdf
  • Filesize: 0.51 MB
  • 12 pages

Document Identifiers

Author Details

Arnaud Durand
Johannes Ebbing
Juha Kontinen
Heribert Vollmer

Cite AsGet BibTex

Arnaud Durand, Johannes Ebbing, Juha Kontinen, and Heribert Vollmer. Dependence logic with a majority quantifier. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 252-263, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.FSTTCS.2011.252

Abstract

We study the extension of dependence logic D by a majority quantifier 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, D(M) captures the complexity class counting hierarchy.
Keywords
  • dependence logic
  • counting hierarchy
  • majority quantifier
  • second order logic
  • descriptive complexity
  • finite model theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail