Extraction de sous-formules minimales inconsistantes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Extraction de sous-formules minimales inconsistantes

Résumé

Une sous-formule minimale inconsistante (Minimally Unsatisfiable Subformula ou MUS en anglais) représente la plus petite cause d'incohérence d'une instance SAT en terme de nombre de clauses. Extraire un ou plusieurs MUS s'avère donc très utile, car ceux-ci circonscrivent les sources d'inconsistance d'une formule CNF. Dans ce papier, une nouvelle méta-heuristique permettant l'approximation ou le calcul d'un MUS est présentée. Une comparaison avec les méthodes les plus compétitives est effectuée, et montre que le plus souvent, en pratique, cette approche surpasse les résultats obtenus par les autres méthodes existantes.
Fichier principal
Vignette du fichier
01.pdf (159.7 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00085769 , version 1 (14-07-2006)

Identifiants

  • HAL Id : inria-00085769 , version 1

Citer

Eric Gregoire, Bertrand Mazure, Cédric Piette. Extraction de sous-formules minimales inconsistantes. Journées Francophones de Programmation par Contraintes, 2006, Ecole des Mines d'Alès - Nîmes. ⟨inria-00085769⟩
60 Consultations
301 Téléchargements

Partager

Gmail Facebook X LinkedIn More