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

Approximation d'ensembles horn strong backdoor par recherche locale

Résumé : Dans ce papier, nous proposons une nouvelle approche pour calculer un strong backdoor pour des formules mises sous forme normale conjonctive (CNF). Elle est basée sur une utilisation originale d'une méthode de recherche locale qui fournit un renommage maximisant la sous-formule horn-renommable d'une CNF donnée. Plus précisément, à chaque étape, on choisit de renommer la variable qui fait le plus diminuer le nombre de clauses non-horn. S'il ne reste plus de clauses strictement positives (ou strictement négatives) ou de clauses non-horn dans la formule, notre méthode répond au problème de satisfaisabilité de la formule originale; sinon, on utilise la plus petite sous-formule qui ne soit pas de horn pour en extraire un ensemble de variables (strong backdoor) tel qu'une fois ces variables instanciées, le reste du problème appartient à une classe polynômiale. Les premiers résultats expérimentaux montrent que notre approche est prometteuse sur un grand nombre d'instances SAT.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085807
Contributor : Laurent Henocque Connect in order to contact the contributor
Submitted on : Friday, July 14, 2006 - 3:17:42 PM
Last modification on : Friday, October 22, 2021 - 3:34:33 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:09:44 AM

File

Identifiers

  • HAL Id : inria-00085807, version 1

Citation

Lionel Paris, Richard Ostrowski, Lakhdar Saïs, Pierre Siegel. Approximation d'ensembles horn strong backdoor par recherche locale. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085807⟩

Share

Metrics

Record views

109

Files downloads

267