Skip to content

Research at St Andrews

Symmetry and consistency

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

DOI

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.

Close

Details

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2005
Subtitle of host publicationProceedings of the 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005
EditorsPeter van Beek
PublisherSpringer-Verlag
Pages271-285
Number of pages15
ISBN (Electronic)978-3-540-29238-8
DOIs
Publication statusPublished - 2005
EventPrinciples and Practice of Constraint Programming - CP 2005 - Sitge, Spain
Duration: 1 Oct 20055 Oct 2005

Publication series

NameLecture Notes in Computer Science
Volume3709
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferencePrinciples and Practice of Constraint Programming - CP 2005
CountrySpain
CitySitge
Period1/10/055/10/05

    Research areas

  • SUFFICIENT CONDITION, SEARCH

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 conferencePaper

  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: 2379306

Top