Skip to content

Research at St Andrews

Groupoids and Conditional Symmetry

Research output: Contribution to conferencePaper

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 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.

Close

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Symmetry and consistency

    Gent, I. P., Kelsey, T., Linton, S. & Roney-Dougal, C., 2005, Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. van Beek, P. (ed.). Springer-Verlag, p. 271-285 15 p. (Lecture Notes in Computer Science; vol. 3709).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. Tractable Symmetry Breaking using Restricted Search Trees

    Roney-Dougal, C. M., Gent, I. P., Kelsey, T. W. & Linton, S. A., Aug 2004, ECAI 2004: 16th European Conference on Artificial Intelligence, August 22-27, 2004, Valencia, Spain. López de Mántaras, R. & Saitta, L. (eds.). IOS Press, p. 211-215 5 p. (Frontiers in artificial intelligence and applications; vol. 110).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Qualitative modelling via constraint programming

    Kelsey, T., Kotthoff, L., Jefferson, C. A., Linton, S. A., Miguel, I. J., Nightingale, P. & Gent, I. P., Apr 2014, In : Constraints. 19, 2, p. 163-173

    Research output: Contribution to journalArticle

  4. Conditional symmetry breaking

    Gent, I. P., Kelsey, T., Linton, S. A., McDonald, I., Miguel, I. & Smith, B. M., Oct 2005, Principles and practice of constraint programming--CP 2005: 11th international conference, CP 2005, Sitges, Spain, October 1-5, 2005 : Proceedings . Van Beek, P. (ed.). Springer, p. 256-270 15 p. (Lecture notes in computer science; vol. 3709).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

ID: 389594

Top