Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085769
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 8:43:30 AM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:07:43 AM

File

Identifiers

  • HAL Id : inria-00085769, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

180

Files downloads

587