Excluding symmetries in constraint-based search

Rolf Backofen; Sebastian Will

doi:10.1007/978-3-540-48085-3_6

Excluding symmetries in constraint-based search

Rolf Backofen
, Sebastian Will

Universität München

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

Abstract

We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings
Editors	Joxan Jaffar
Publisher	Springer Verlag
Pages	73-87
Number of pages	15
ISBN (Print)	3540666265, 9783540666264
DOIs	https://doi.org/10.1007/978-3-540-48085-3_6
Publication status	Published - 1 Jan 1999
Externally published	Yes
Event	5th International Conference on Principles and Practice of Constraint Programming, CP 1999 - Alexandria, United States Duration: 11 Oct 1999 → 14 Oct 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1713
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Conference on Principles and Practice of Constraint Programming, CP 1999
Country/Territory	United States
City	Alexandria
Period	11/10/99 → 14/10/99

Access to Document

10.1007/978-3-540-48085-3_6

Cite this

Backofen, R., & Will, S. (1999). Excluding symmetries in constraint-based search. In J. Jaffar (Ed.), Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings (pp. 73-87). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1713). Springer Verlag. https://doi.org/10.1007/978-3-540-48085-3_6

Backofen, Rolf ; Will, Sebastian. / Excluding symmetries in constraint-based search. Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. editor / Joxan Jaffar. Springer Verlag, 1999. pp. 73-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{906aae1a6474478787ef6b1b2aeb0aa6,

title = "Excluding symmetries in constraint-based search",

abstract = "We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.",

author = "Rolf Backofen and Sebastian Will",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 5th International Conference on Principles and Practice of Constraint Programming, CP 1999 ; Conference date: 11-10-1999 Through 14-10-1999",

year = "1999",

month = jan,

day = "1",

doi = "10.1007/978-3-540-48085-3\_6",

language = "English",

isbn = "3540666265",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "73--87",

editor = "Joxan Jaffar",

booktitle = "Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings",

}

Backofen, R & Will, S 1999, Excluding symmetries in constraint-based search. in J Jaffar (ed.), Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1713, Springer Verlag, pp. 73-87, 5th International Conference on Principles and Practice of Constraint Programming, CP 1999, Alexandria, United States, 11/10/99. https://doi.org/10.1007/978-3-540-48085-3_6

Excluding symmetries in constraint-based search. / Backofen, Rolf; Will, Sebastian.
Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. ed. / Joxan Jaffar. Springer Verlag, 1999. p. 73-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1713).

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

TY - GEN

T1 - Excluding symmetries in constraint-based search

AU - Backofen, Rolf

AU - Will, Sebastian

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1999.

PY - 1999/1/1

Y1 - 1999/1/1

N2 - We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.

AB - We introduce a new method for excluding symmetries in constraint based search. To our knowledge, it is the first declarative method that can be applied to arbitrary symmetries. Our method is based on the notion of symmetric constraints, which are used in our modification of a general constraint based search algorithm. The method does not influence the search strategy. Furthermore, it can be used with either the full set of symmetries, or with an subset of all symmetries. We proof correctness, completeness and symmetry exclusion properties of our method. We then show how to apply the method in the special case of geometric symmetries (rotations and reflections) and permutation symmetries. Furthermore, we give results from practical applications.

UR - https://www.scopus.com/pages/publications/84957363249

U2 - 10.1007/978-3-540-48085-3_6

DO - 10.1007/978-3-540-48085-3_6

M3 - Conference contribution

AN - SCOPUS:84957363249

SN - 3540666265

SN - 9783540666264

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 73

EP - 87

BT - Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings

A2 - Jaffar, Joxan

PB - Springer Verlag

T2 - 5th International Conference on Principles and Practice of Constraint Programming, CP 1999

Y2 - 11 October 1999 through 14 October 1999

ER -

Backofen R, Will S. Excluding symmetries in constraint-based search. In Jaffar J, editor, Principles and Practice of Constraint Programming – CP 1999 - 5th International Conference, CP 1999, Proceedings. Springer Verlag. 1999. p. 73-87. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-48085-3_6

Excluding symmetries in constraint-based search

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this