Skip to content

Research at St Andrews

New developments in symmetry breaking in search using computational group theory

Research output: Contribution to conferencePaperpeer-review

DOI

Standard

New developments in symmetry breaking in search using computational group theory. / Kelsey, Thomas William; Linton, Stephen Alexander; Roney-Dougal, Colva Mary.

2004. 199-210.

Research output: Contribution to conferencePaperpeer-review

Harvard

Kelsey, TW, Linton, SA & Roney-Dougal, CM 2004, 'New developments in symmetry breaking in search using computational group theory', pp. 199-210. https://doi.org/10.1007/b100361

APA

Kelsey, T. W., Linton, S. A., & Roney-Dougal, C. M. (2004). New developments in symmetry breaking in search using computational group theory. 199-210. https://doi.org/10.1007/b100361

Vancouver

Kelsey TW, Linton SA, Roney-Dougal CM. New developments in symmetry breaking in search using computational group theory. 2004. https://doi.org/10.1007/b100361

Author

Kelsey, Thomas William ; Linton, Stephen Alexander ; Roney-Dougal, Colva Mary. / New developments in symmetry breaking in search using computational group theory.

Bibtex - Download

@conference{8d5507fdbdf842439807d8e6e6f060af,
title = "New developments in symmetry breaking in search using computational group theory",
abstract = "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.",
author = "Kelsey, {Thomas William} and Linton, {Stephen Alexander} and Roney-Dougal, {Colva Mary}",
note = "Proceedings of the 7th International Conference on Artificial Intelligence and Symbolic Computation, Lecture Notes in Computer Science",
year = "2004",
doi = "10.1007/b100361",
language = "English",
pages = "199--210",

}

RIS (suitable for import to EndNote) - Download

TY - CONF

T1 - New developments in symmetry breaking in search using computational group theory

AU - Kelsey, Thomas William

AU - Linton, Stephen Alexander

AU - Roney-Dougal, Colva Mary

N1 - Proceedings of the 7th International Conference on Artificial Intelligence and Symbolic Computation, Lecture Notes in Computer Science

PY - 2004

Y1 - 2004

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

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

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

UR - http://www.springerlink.com/content/lq6m4n3xepy7qh2p/?p=baaad8f1cc7244ebab59572673a12e5c&pi=29

U2 - 10.1007/b100361

DO - 10.1007/b100361

M3 - Paper

SP - 199

EP - 210

ER -

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

Top