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: http://doi.org/10.1007/978-3-540-30502-6_24
Related URL: http://dx.doi.org/10.1007/978-3-540-30502-6_24
Abstract
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
