DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.252

Dependence logic with a majority quantifier

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

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{durand_et_al:LIPIcs.FSTTCS.2011.252,
  author =	{Durand, Arnaud and Ebbing, Johannes and Kontinen, Juha and Vollmer, Heribert},
  title =	{{Dependence logic with a majority quantifier}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{252--263},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.252},
  URN =		{urn:nbn:de:0030-drops-33467},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.252},
  annote =	{Keywords: dependence logic, counting hierarchy, majority quantifier, second order logic, descriptive complexity, finite model theory}
}

Search Results

Documents authored by Ebbing, Johannes

Dependence logic with a majority quantifier

Abstract

Cite as

Thanks for your feedback!

Could not send message