Symmetry and consistency

I P  Gent; T  Kelsey; S  Linton; C  Roney-Dougal

doi:10.1007/11564751_22

Symmetry and consistency

I P Gent, T Kelsey, S Linton, C Roney-Dougal

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce a novel and exciting research area: symmetrising levels of consistency to produce stronger forms of consistency and more efficient mechanisms for establishing them. We propose new levels of consistency for Constraint Satisfaction Problems (CSPs) incorporating the symmetry group of a CSP. We first define Sym(i, j) -consistency, show that even Sym(1,0)-consistency can prune usefully, and study some consequences of maintaining Sym(i, 0)consistency. We then present pseudocode for SymPath consistency, and a symmetrised version of singleton consistency, before presenting experimental evidence of these algorithms' practical effectiveness. With this contribution we establish the study of symmetry-based levels of consistency of CSPs.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - CP 2005
Subtitle of host publication	Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005
Editors	Peter van Beek
Publisher	Springer-Verlag
Pages	271-285
Number of pages	15
ISBN (Electronic)	978-3-540-29238-8
DOIs	https://doi.org/10.1007/11564751_22
Publication status	Published - 2005
Event	Principles and Practice of Constraint Programming - CP 2005 - Sitge, Spain Duration: 1 Oct 2005 → 5 Oct 2005

Publication series

Name	Lecture Notes in Computer Science
Volume	3709
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Principles and Practice of Constraint Programming - CP 2005
Country/Territory	Spain
City	Sitge
Period	1/10/05 → 5/10/05

Keywords

SUFFICIENT CONDITION
SEARCH

Access to Document

10.1007/11564751_22

Cite this

Gent, I. P., Kelsey, T., Linton, S., & Roney-Dougal, C. (2005). Symmetry and consistency. In P. van Beek (Ed.), Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005 (pp. 271-285). (Lecture Notes in Computer Science; Vol. 3709). Springer-Verlag. https://doi.org/10.1007/11564751_22

@inproceedings{300eec70931d4f089398e7c2c60415ab,

title = "Symmetry and consistency",

abstract = "We introduce a novel and exciting research area: symmetrising levels of consistency to produce stronger forms of consistency and more efficient mechanisms for establishing them. We propose new levels of consistency for Constraint Satisfaction Problems (CSPs) incorporating the symmetry group of a CSP. We first define Sym(i, j) -consistency, show that even Sym(1,0)-consistency can prune usefully, and study some consequences of maintaining Sym(i, 0)consistency. We then present pseudocode for SymPath consistency, and a symmetrised version of singleton consistency, before presenting experimental evidence of these algorithms' practical effectiveness. With this contribution we establish the study of symmetry-based levels of consistency of CSPs.",

keywords = "SUFFICIENT CONDITION, SEARCH",

author = "Gent, {I P} and T Kelsey and S Linton and C Roney-Dougal",

year = "2005",

doi = "10.1007/11564751_22",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer-Verlag",

pages = "271--285",

editor = "{van Beek}, Peter",

booktitle = "Principles and Practice of Constraint Programming - CP 2005",

address = "Germany",

note = "Principles and Practice of Constraint Programming - CP 2005 ; Conference date: 01-10-2005 Through 05-10-2005",

}

Gent, IP , Kelsey, T , Linton, S & Roney-Dougal, C 2005, Symmetry and consistency. in P van Beek (ed.), Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. Lecture Notes in Computer Science, vol. 3709, Springer-Verlag, pp. 271-285, Principles and Practice of Constraint Programming - CP 2005, Sitge, Spain, 1/10/05. https://doi.org/10.1007/11564751_22

Symmetry and consistency. / Gent, I P ; Kelsey, T ; Linton, S et al.
Principles and Practice of Constraint Programming - CP 2005: Proceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005. ed. / Peter van Beek. Springer-Verlag, 2005. p. 271-285 (Lecture Notes in Computer Science; Vol. 3709).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Symmetry and consistency

AU - Gent, I P

AU - Kelsey, T

AU - Linton, S

AU - Roney-Dougal, C

PY - 2005

Y1 - 2005

N2 - We introduce a novel and exciting research area: symmetrising levels of consistency to produce stronger forms of consistency and more efficient mechanisms for establishing them. We propose new levels of consistency for Constraint Satisfaction Problems (CSPs) incorporating the symmetry group of a CSP. We first define Sym(i, j) -consistency, show that even Sym(1,0)-consistency can prune usefully, and study some consequences of maintaining Sym(i, 0)consistency. We then present pseudocode for SymPath consistency, and a symmetrised version of singleton consistency, before presenting experimental evidence of these algorithms' practical effectiveness. With this contribution we establish the study of symmetry-based levels of consistency of CSPs.

AB - We introduce a novel and exciting research area: symmetrising levels of consistency to produce stronger forms of consistency and more efficient mechanisms for establishing them. We propose new levels of consistency for Constraint Satisfaction Problems (CSPs) incorporating the symmetry group of a CSP. We first define Sym(i, j) -consistency, show that even Sym(1,0)-consistency can prune usefully, and study some consequences of maintaining Sym(i, 0)consistency. We then present pseudocode for SymPath consistency, and a symmetrised version of singleton consistency, before presenting experimental evidence of these algorithms' practical effectiveness. With this contribution we establish the study of symmetry-based levels of consistency of CSPs.

KW - SUFFICIENT CONDITION

KW - SEARCH

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

UR - http://www.springerlink.com/content/b85w057261026678/

U2 - 10.1007/11564751_22

DO - 10.1007/11564751_22

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 271

EP - 285

BT - Principles and Practice of Constraint Programming - CP 2005

A2 - van Beek, Peter

PB - Springer-Verlag

T2 - Principles and Practice of Constraint Programming - CP 2005

Y2 - 1 October 2005 through 5 October 2005

ER -

Symmetry and consistency

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this

Symmetry and consistency

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this