Technical Report 2005-034

Detecting Symmetries in Relational Models of CSPs

Maria Eriksson

November 2005

Abstract:
This master's thesis studies symmetry detection in constraint satisfaction problems (CSPs). After modelling some well-known CSPs in a relational language, the symmetries of the single constraints in the models are studied. These results are then transformed into general patterns for symmetry detection. When the symmetries of the single constraints have been detected, symmetries for complete CSPs, with one or more constraints, are derived compositionally. This work deals with value as well as variable interchangeability.

Note: M.Sc. thesis

Available as PDF (281 kB, no cover)

Download BibTeX entry.