Projects per year
Abstract
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 subGroupoid forms a group, and, for this case, present an algorithm for breaking all conditional symmetries that arise at a search node. Our algorithm is polynomialtime 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  823830 
DOIs  
Publication status  Published  Sept 2007 
Fingerprint
Dive into the research topics of 'Groupoids and Conditional Symmetry'. Together they form a unique fingerprint.Projects
 1 Finished

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
1/09/05 → 31/08/10
Project: Standard