Local Consistencies in SAT - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

Local Consistencies in SAT

Emmanuel Hébrard
Toby Walsh
  • Fonction : Auteur
  • PersonId : 1055916

Résumé

We introduce some new mappings of constraint satisfaction problems into propositional satisfiability. These encodings generalize most of the existing encodings. Unit propagation on those encodings is the same as establishing relational k-arc consistency on the original problem. They can also be used to establish (i,j)-consistency on binary constraints. Experiments show that these encodings are an effective method for enforcing such consistencies, that can lead to a reduction in runtimes at the phase transition in most cases. Compared to the more traditional (direct) encoding, the search tree can be greatly pruned.
Fichier principal
Vignette du fichier
sat03.pdf (2.12 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-00269776 , version 1 (12-10-2019)

Identifiants

  • HAL Id : lirmm-00269776 , version 1

Citer

Christian Bessiere, Emmanuel Hébrard, Toby Walsh. Local Consistencies in SAT. SAT: Theory and Applications of Satisfiability Testing, May 2003, Santa Margherita Ligure, Italy. pp.400-407. ⟨lirmm-00269776⟩
147 Consultations
8 Téléchargements

Partager

Gmail Facebook X LinkedIn More