License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8057
URL: http://drops.dagstuhl.de/opus/volltexte/2006/805/
Schnoor, Henning ; Schnoor, Ilka

New Algebraic Tools for Constraint Satisfaction

pdf-format:
Dokument 1.pdf (274 KB)

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:DSP:2006:805,
  author =	{Henning Schnoor and Ilka Schnoor},
  title =	{New Algebraic Tools for Constraint Satisfaction},
  booktitle =	{Complexity of Constraints},
  year =	{2006},
  editor =	{Nadia Creignou and Phokion Kolaitis and Heribert Vollmer},
  number =	{06401},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/805},
  annote =	{Keywords: Constraints, Partial Clones, Galois Correspondence}
}

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

DROPS-Home | Fulltext Search | Imprint Published by LZI