Maximal Falsifiability: definitions, algorithms, and applications

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

doi:10.1007/978-3-642-45221-5_30

Maximal Falsifiability: definitions, algorithms, and applications

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

10 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 language	English
Title of host publication	Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings
Publisher	Springer
Pages	439-456
Number of pages	18
Volume	8312
ISBN (Print)	9783642452208
DOIs	https://doi.org/10.1007/978-3-642-45221-5_30
Publication status	Published - 2013
Externally published	Yes
Event	International Conference on Logic Programming and Automated Reasoning 2013 - Stellenbosch, South Africa Duration: 14 Dec 2013 → 19 Dec 2013 Conference number: 19th

Publication series

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

Conference

Conference	International Conference on Logic Programming and Automated Reasoning 2013
Abbreviated title	LPAR 2013
Country/Territory	South Africa
City	Stellenbosch
Period	14/12/13 → 19/12/13

Access to Document

10.1007/978-3-642-45221-5_30

Cite this

Ignatiev, A., Morgado, A., Planes, J., & Marques-Silva, J. (2013). Maximal Falsifiability: definitions, algorithms, and applications. In Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings (Vol. 8312, pp. 439-456). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8312 LNCS). Springer. https://doi.org/10.1007/978-3-642-45221-5_30

Ignatiev, Alexey ; Morgado, Antonio ; Planes, Jordi et al. / Maximal Falsifiability : definitions, algorithms, and applications. Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings. Vol. 8312 Springer, 2013. pp. 439-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0d23068cff1b4f938d5156d24c7000a6,

title = "Maximal Falsifiability: definitions, algorithms, and applications",

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.",

author = "Alexey Ignatiev and Antonio Morgado and Jordi Planes and Joao Marques-Silva",

year = "2013",

doi = "10.1007/978-3-642-45221-5_30",

language = "English",

isbn = "9783642452208",

volume = "8312",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "439--456",

booktitle = "Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings",

note = "International Conference on Logic Programming and Automated Reasoning 2013, LPAR 2013 ; Conference date: 14-12-2013 Through 19-12-2013",

}

Ignatiev, A, Morgado, A, Planes, J & Marques-Silva, J 2013, Maximal Falsifiability: definitions, algorithms, and applications. in Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings. vol. 8312, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8312 LNCS, Springer, pp. 439-456, International Conference on Logic Programming and Automated Reasoning 2013, Stellenbosch, South Africa, 14/12/13. https://doi.org/10.1007/978-3-642-45221-5_30

Maximal Falsifiability : definitions, algorithms, and applications. / Ignatiev, Alexey; Morgado, Antonio; Planes, Jordi et al.

Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings. Vol. 8312 Springer, 2013. p. 439-456 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8312 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

TY - GEN

T1 - Maximal Falsifiability

T2 - International Conference on Logic Programming and Automated Reasoning 2013

AU - Ignatiev, Alexey

AU - Morgado, Antonio

AU - Planes, Jordi

AU - Marques-Silva, Joao

N1 - Conference code: 19th

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893969047&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45221-5_30

DO - 10.1007/978-3-642-45221-5_30

M3 - Conference Paper

SN - 9783642452208

VL - 8312

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 439

EP - 456

BT - Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings

PB - Springer

Y2 - 14 December 2013 through 19 December 2013

ER -

Ignatiev A, Morgado A, Planes J, Marques-Silva J. Maximal Falsifiability: definitions, algorithms, and applications. In Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings. Vol. 8312. Springer. 2013. p. 439-456. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-45221-5_30

Maximal Falsifiability: definitions, algorithms, and applications

Abstract

Publication series

Conference

Access to Document

Other files and links

Maximal falsifiability

Cite this