Symmetry and consistency

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

1 Citation (Scopus)

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 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
Country/TerritorySpain
CitySitge
Period1/10/055/10/05

Keywords

  • SUFFICIENT CONDITION
  • SEARCH

Fingerprint

Dive into the research topics of 'Symmetry and consistency'. Together they form a unique fingerprint.

Cite this