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 <>
Submitted on : Friday, June 1, 2007 - 4:46:00 PM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
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

110

Files downloads

168