A resolution calculus for MinSAT - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Logic Journal of the IGPL Année : 2021

A resolution calculus for MinSAT

Résumé

The logical calculus for SAT are not valid for MaxSAT and MinSAT because they preserve satisfiability but not the number of unsatisfied clauses. To overcome this drawback, a MaxSAT resolution rule preserving the number of unsatisfied clauses was defined in the literature. This rule is complete for MaxSAT when it is applied following a certain strategy. In this paper we first prove that the MaxSAT resolution rule also provides a complete calculus for MinSAT if it is applied following the strategy proposed here. We then describe an exact variable elimination algorithm for MinSAT based on that rule. Finally, we show how the results for Boolean MinSAT can be extended to solve the MinSAT problem of the multiple-valued clausal forms known as signed conjunctive normal form formulas.
Fichier non déposé

Dates et versions

hal-03636410 , version 1 (10-04-2022)

Identifiants

Citer

Chu-Min Li, Fan Xiao, Felip Manya. A resolution calculus for MinSAT. Logic Journal of the IGPL, 2021, 29 (1), pp.28-44. ⟨10.1093/jigpal/jzz028⟩. ⟨hal-03636410⟩
30 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More