1 Search Results for "Madelaine, Florent R."

Document

DOI: 10.4230/LIPIcs.MFCS.2018.11

Consistency for Counting Quantifiers

Authors: Florent R. Madelaine and Barnaby Martin

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard.

Cite as

Florent R. Madelaine and Barnaby Martin. Consistency for Counting Quantifiers. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{madelaine_et_al:LIPIcs.MFCS.2018.11,
  author =	{Madelaine, Florent R. and Martin, Barnaby},
  title =	{{Consistency for Counting Quantifiers}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.11},
  URN =		{urn:nbn:de:0030-drops-95931},
  doi =		{10.4230/LIPIcs.MFCS.2018.11},
  annote =	{Keywords: Quantified Constraints, Constraint Satisfaction, Logic in Computer Science, Universal Algebra, Computational Complexity}
}

Refine by Author
1 Madelaine, Florent R.
1 Martin, Barnaby

Refine by Classification
1 Theory of computation → Constraint and logic programming

Refine by Keyword
1 Computational Complexity
1 Constraint Satisfaction
1 Logic in Computer Science
1 Quantified Constraints
1 Universal Algebra

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Madelaine, Florent R."

Consistency for Counting Quantifiers

Abstract

Cite as

Thanks for your feedback!

Could not send message