Research output: Contribution to conference › Paper › peer-review
Ian Philip Gent, Thomas William Kelsey, Stephen Alexander Linton, J Pearson, Colva Mary Roney-Dougal, Christian Bessiere
We introduce groupoids - generalisations of groups in which not all pairs of elements may be multiplied, or, equivalently, categories in which all morphisms are invertible - as the appropriate algebraic structures for dealing with conditional symmetries in Constraint Satisfaction Problems (CSPs). We formally define the Full Conditional Symmetry Groupoid associated with any CSP, giving bounds for the number of elements that this groupoid can contain. We describe conditions under which a Conditional Symmetry sub-Groupoid forms a group, and, for this case, present an algorithm for breaking all conditional symmetries that arise at a search node. Our algorithm is polynomial-time when there is a corresponding algorithm for the type of group involved. We prove that our algorithm is both sound and complete - neither gaining nor losing solutions.
Original language | English |
---|---|
Pages | 823-830 |
DOIs | |
Publication status | Published - Sep 2007 |
Additional links |
Discover related content
Find related publications, people, projects and more using interactive charts.
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Research output: Contribution to journal › Article › peer-review
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Research output: Contribution to conference › Paper › peer-review
ID: 389594