| Title: |
Max-réfutations et oracles SAT |
| Authors: |
Py, Matthieu; Cherif, Mohamed Sami; Habet, Djamal |
| Contributors: |
COntraintes, ALgorithmes et Applications (COALA); Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS); Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS) |
| Source: |
JFPC 2022 ; https://amu.hal.science/hal-03737731 ; JFPC 2022, Jun 2022, Saint-Etienne, France |
| Publisher Information: |
CCSD |
| Publication Year: |
2022 |
| Collection: |
Université de Toulon: HAL |
| Subject Terms: |
Max-SAT; Résolution; Max-Réfutation; [INFO]Computer Science [cs] |
| Subject Geographic: |
Saint-Etienne; France |
| Description: |
International audience ; Adapter une réfutation par résolution en max-réfutation sans en augmenter considérablement sa taille est une question ouverte depuis l'introduction de la max-résolution. Cet article contribue à cette problématique en proposant un algorithme nommé algorithme de génération de remplaçants, capable d'adapter n'importe quelle réfutation par résolution en max-réfutation grâce à des appels à un oracle SAT. En particulier, on démontre que cet algorithme adapte efficacement les motifs en diamant, dont l'adaptation est exponentielle dans la littérature. Cet article résume le travail publié à la conférence ICTAI 2021 [3]. |
| Document Type: |
conference object |
| Language: |
French |
| Availability: |
https://amu.hal.science/hal-03737731; https://amu.hal.science/hal-03737731v1/document; https://amu.hal.science/hal-03737731v1/file/JFPC_2022___Max_refutations_et_oracles_SAT.pdf |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.7BD31F |
| Database: |
BASE |