Minimal Unsatisfiable Sets: Classification and Bounds

Dasgupta, Sudeshna ; Chandru, Vijay (2004) Minimal Unsatisfiable Sets: Classification and Bounds Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making, 3321 . pp. 330-342. ISSN 0302-9743

Full text not available from this repository.

Official URL:

Related URL:


Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

Item Type:Article
Source:Copyright of this article belongs to Springer Nature Switzerland AG
Keywords:Boolean formulas;propositional logic;satisfiability;Minimal Unsatisfiable Sets
ID Code:132581
Deposited On:20 Dec 2022 05:28
Last Modified:20 Dec 2022 05:28

Repository Staff Only: item control page