Florent Madelaine
Consistency for counting quantifiers
Madelaine, Florent; Martin, Barnaby
Authors
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Contributors
Igor Potapov
Editor
Paul Spirakis
Editor
James Worrell
Editor
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.
Citation
Madelaine, F., & Martin, B. (2018). Consistency for counting quantifiers. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (11:1-11:13). https://doi.org/10.4230/lipics.mfcs.2018.11
Conference Name | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). |
---|---|
Conference Location | Liverpool, UK |
Start Date | Aug 27, 2018 |
End Date | Aug 31, 2018 |
Acceptance Date | Jun 13, 2018 |
Publication Date | Aug 31, 2018 |
Deposit Date | Jul 12, 2018 |
Publicly Available Date | Jun 27, 2019 |
Volume | 117 |
Pages | 11:1-11:13 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series ISSN | 1868-8969 |
Book Title | 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). |
DOI | https://doi.org/10.4230/lipics.mfcs.2018.11 |
Public URL | https://durham-repository.worktribe.com/output/1145134 |
Files
Published Conference Proceeding
(465 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Accepted Conference Proceeding
(559 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© B. Martin and F. R. Madelaine; licensed under Creative Commons License CC-BY
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search