HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Une nouvelle méthode hybride pour calculer tous les MSS et tous les MUS

Résumé : Dans ce papier, nous présentons une nouvelle technique complète permettant le calcul des sous-formules maximales consistantes (MSS) et des formules minimales inconsistantes (MUS) d'un ensemble de clauses booléennes. Cette approche améliore la meilleure technique complète connue de plusieurs manières. Elle utilise à la fois une recherche locale peu coûteuse en ressources et le nouveau concept de clause critique pour améliorer un algorithme complet proposé par Liffiton et Sakallah. Cette hybridation permet l'obtention de gains exponentiels. Ainsi, des résultats expérimentaux montrent que cette nouvelle approche dépasse la meilleure méthode proposée jusque ici.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151153
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 4:46:00 PM
Last modification on : Thursday, January 13, 2022 - 3:14:05 PM
Long-term archiving on: : Thursday, April 8, 2010 - 6:43:02 PM

File

8.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151153, version 1

Collections

Citation

Eric Grégoire, Bertrand Mazure, Cédric Piette. Une nouvelle méthode hybride pour calculer tous les MSS et tous les MUS. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00151153⟩

Share

Metrics

Record views

50

Files downloads

95