Skip to Main content Skip to Navigation
Conference papers

A First Practical Algorithm for High Levels of Relational Consistency

Shant Karakashian 1 Robert J. Woodward 1 Christopher Reeson 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. In this paper, we study the relational consistency property R(∗,m)C, which is equivalent to m-wise consistency proposed in rela- tional databases. We also define wR(∗,m)C, a weaker variant of this property. We propose an algorithm for enforcing these properties on a Constraint Satisfaction Problem by tighten- ing the existing relations and without introducing new ones. We empirically show that wR(∗,m)C solves in a backtrack- free manner all the instances of some CSP benchmark classes, thus hinting at the tractability of those classes.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00558132
Contributor : Martine Peridier <>
Submitted on : Friday, January 21, 2011 - 9:54:44 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

Identifiers

  • HAL Id : lirmm-00558132, version 1

Collections

Citation

Shant Karakashian, Robert J. Woodward, Christopher Reeson, Berthe Y. Choueiry, Christian Bessière. A First Practical Algorithm for High Levels of Relational Consistency. AAAI Conference on Artificial Intelligence, Jul 2010, Atlanta, GA, United States. pp.101-107. ⟨lirmm-00558132⟩

Share

Metrics

Record views

165

Files downloads

8