DagSemProc.06401.7.pdf
- Filesize: 274 kB
- 18 pages
Document
New Algebraic Tools for Constraint Satisfaction
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 6401
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2006-11-15
Cite AsGet BibTex
Henning Schnoor and Ilka Schnoor. New Algebraic Tools for Constraint Satisfaction. In Complexity of Constraints. Dagstuhl Seminar Proceedings, Volume 6401, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
https://doi.org/10.4230/DagSemProc.06401.7
https://doi.org/10.4230/DagSemProc.06401.7
Abstract
The Galois correspondence involving polymorphisms and co-clones
has received a lot of attention in regard to constraint satisfaction problems.
However, it fails if we are interested in a reduction giving equivalence
instead of only satisfiability-equivalence. We show how a similar
Galois connection involving weaker closure operators can be applied for
these problems. As an example of the usefulness of our construction, we
show how to obtain very short proofs of complexity classifications in this
context.
Keywords
- Constraints
- Partial Clones
- Galois Correspondence
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads