Skip to content

Research at St Andrews

New developments in symmetry breaking in search using computational group theory

Research output: Contribution to conferencePaperpeer-review



Symmetry-breaking in constraint satisfaction problems is a well-established area of AI research which has recently developed strong interactions with symbolic computation, in the form of computational group theory. GE-trees axe a new conceptual abstraction, providing low-degree polynomial time methods for breaking value symmetries in constraint satisfication problems. In this paper we analyse the structure of symmetry groups of constraint satisfaction problems, and implement several combinations of GE-trees and the classical SBDD method for breaking all symmetries. We prove the efficacy of our techniques, and present preliminary experimental evidence of their practical efficiency.


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

View graph of relations

Related by author

  1. Groupoids and Conditional Symmetry

    Gent, I. P., Kelsey, T. W., Linton, S. A., Pearson, J., Roney-Dougal, C. M. & Bessiere, C., Sep 2007, p. 823-830.

    Research output: Contribution to conferencePaperpeer-review

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

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

  4. Polynomial-time proofs that groups are hyperbolic

    Holt, D., Linton, S., Neunhoeffer, M., Parker, R., Pfeiffer, M. & Roney-Dougal, C. M., May 2021, In: Journal of Symbolic Computation. 104, p. 419-475

    Research output: Contribution to journalArticlepeer-review

  5. Towards the calculation of Casimir forces for inhomogeneous planar media

    Xiong, C., Kelsey, T., Linton, S. A. & Leonhardt, U., 1 Oct 2014, Computer Mathematics: 9th Asian Symposium (ASCM2009), Fukuoka, December 2009, 10th Asian Symposium (ASCM2012), Beijing, October 2012, Contributed Papers and Invited Talks. Feng, R., Lee, W. & Sato, Y. (eds.). Springer, p. 171-180

    Research output: Chapter in Book/Report/Conference proceedingChapter

ID: 255600