Maximal falsifiability

Alexey Ignatiev, Antonio Morgado, Jordi Planes, Joao Marques-Silva

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

Similarly to Maximum Satisfiability (MaxSAT), Minimum Satisfiability (MinSAT) is an optimization extension of the Boolean Satisfiability (SAT) decision problem. In recent years, both problems have been studied in terms of exact and approximation algorithms. In addition, the MaxSAT problem has been characterized in terms of Maximal Satisfiable Subsets (MSSes) and Minimal Correction Subsets (MCSes), as well as Minimal Unsatisfiable Subsets (MUSes) and minimal hitting set dualization. However, and in contrast with MaxSAT, no such characterizations exist for MinSAT. This paper addresses this issue by casting the MinSAT problem in a more general framework. The paper studies Maximal Falsifiability, the problem of computing a subset-maximal set of clauses that can be simultaneously falsified, and shows that MinSAT corresponds to the complement of a largest subset-maximal set of simultaneously falsifiable clauses, i.e. the solution of the Maximum Falsifiability (MaxFalse) problem. Additional contributions of the paper include novel algorithms for Maximum and Maximal Falsifiability, as well as minimal hitting set dualization results for the MaxFalse problem. Moreover, the proposed algorithms are validated on practical instances.

Original languageEnglish
Pages (from-to)351-370
Number of pages20
JournalAI Communications
Volume29
Issue number2
DOIs
Publication statusPublished - 2016
Externally publishedYes

Keywords

  • Boolean optimization
  • Maximum falsifiability
  • minimal hitting set duality
  • minimum satisfiability

Cite this

Ignatiev, A., Morgado, A., Planes, J., & Marques-Silva, J. (2016). Maximal falsifiability. AI Communications, 29(2), 351-370. https://doi.org/10.3233/AIC-150685