License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06401.7
URN: urn:nbn:de:0030-drops-8057
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/805/
Go to the corresponding Portal

Schnoor, Henning ; Schnoor, Ilka

New Algebraic Tools for Constraint Satisfaction

pdf-format:
06401.SchnoorIlka.Paper.805.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{schnoor_et_al:DagSemProc.06401.7,
  author =	{Schnoor, Henning and Schnoor, Ilka},
  title =	{{New Algebraic Tools for Constraint Satisfaction}},
  booktitle =	{Complexity of Constraints},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6401},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/805},
  URN =		{urn:nbn:de:0030-drops-8057},
  doi =		{10.4230/DagSemProc.06401.7},
  annote =	{Keywords: Constraints, Partial Clones, Galois Correspondence}
}

Keywords: Constraints, Partial Clones, Galois Correspondence
Collection: 06401 - Complexity of Constraints
Issue Date: 2006
Date of publication: 15.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI