Maximal Falsifiability: definitions, algorithms, and applications

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

8 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 ofMaximal Satisfiable Subsets (MSSes) andMinimal 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
Title of host publicationLogic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings
PublisherSpringer
Pages439-456
Number of pages18
Volume8312
ISBN (Print)9783642452208
DOIs
Publication statusPublished - 2013
Externally publishedYes
EventInternational Conference on Logic Programming and Automated Reasoning 2013 - Stellenbosch, South Africa
Duration: 14 Dec 201319 Dec 2013
Conference number: 19th

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Logic Programming and Automated Reasoning 2013
Abbreviated titleLPAR 2013
CountrySouth Africa
CityStellenbosch
Period14/12/1319/12/13

Cite this