TY - GEN

T1 - Symmetry definitions for constraint satisfaction problems

AU - Cohen, David

AU - Jeavons, Peter

AU - Jefferson, Christopher

AU - Petrie, Karen E.

AU - Smith, Barbara M.

PY - 2005/12/1

Y1 - 2005/12/1

N2 - We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, a.nd show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint Symmetrien. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a. related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

AB - We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, a.nd show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint Symmetrien. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a. related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.

UR - http://www.scopus.com/inward/record.url?scp=33646170054&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33646170054

SN - 3540292381

SN - 9783540292388

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 17

EP - 31

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 11th International Conference on Principles and Practice of Constraint Programming - CP 2005

Y2 - 1 October 2005 through 5 October 2005

ER -