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.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151153
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 16:46:00
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:43:02

Fichier

8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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, 2007, JFPC07. 〈inria-00151153〉

Partager

Métriques

Consultations de la notice

78

Téléchargements de fichiers

113