Minimal unsatisfiable sets: Classification and bounds
Contribuinte(s) |
Maher, JM |
---|---|
Data(s) |
2005
|
Resumo |
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. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/43770/1/Minimal_Unsatisfiable.pdf Chandru, Vijay and Dasgupta, Sudeshna (2005) Minimal unsatisfiable sets: Classification and bounds. In: 9th Asian Computing Science Conference, DEC 08-10, 2004, Chiang Mai, THAILAND. |
Publicador |
Springer |
Relação |
http://www.springerlink.com/content/hv5xvqk36lbggkxp/ http://eprints.iisc.ernet.in/43770/ |
Palavras-Chave | #Others |
Tipo |
Conference Paper PeerReviewed |