Résolution Etendue par Substitution Dynamique des Fonctions Booléennes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Résolution Etendue par Substitution Dynamique des Fonctions Booléennes

Said Jabbour
Lakhdar Saïs

Résumé

Ce travail présente une technique originale de substitution dynamique des fonctions booléennes. Il détecte premièrement un ensemble de fonctions booléennes dans la formule booléenne sous forme normale conjonctive (CNF). Ces fonctions sont ensuite utilisées pour réduire la taille des différentes clauses apprises en substituant les arguments d'entrée par les arguments de sortie. Ceci conduit à une façon originale d'intégrer une forme restreinte de réesolution étendue, l'un des plus puissants systèmes de preuve par résolution. En effet, la plupart des fonctions booléennes extraites correspondent à celles introduites au cours de la phase d'encodage CNF en appliquant le principe d'extension Tseitin. Substituer les entrées par les sorties peut être vu comme une façon élégante d'imiter la résolution étendue avec la manipulation des sous-formules. Des expérimentations préliminaires montrent la faisabilité de notre approche sur certaines classes d'instances SAT prises des récentes competitions SAT et SAT-Race.
Fichier principal
Vignette du fichier
jfpc2012SubFonctions.pdf (208.72 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00820039 , version 1 (03-05-2013)

Identifiants

  • HAL Id : hal-00820039 , version 1

Citer

Said Jabbour, Jerry Lonlac, Lakhdar Saïs. Résolution Etendue par Substitution Dynamique des Fonctions Booléennes. JFPC, May 2012, Toulouse, France. ⟨hal-00820039⟩
64 Consultations
240 Téléchargements

Partager

Gmail Facebook X LinkedIn More