Information processing letters, 2002-11, Vol.84 (3), p.147-151
2002
Volltextzugriff (PDF)
Details
- Autor(en) / Beteiligte
- Titel
- Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency
- Ist Teil von
- Information processing letters, 2002-11, Vol.84 (3), p.147-151
- Ort / Verlag
- Amsterdam: Elsevier B.V
- Erscheinungsjahr
- 2002
- Quelle
- Access via ScienceDirect (Elsevier)
- Beschreibungen/Notizen
- We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ( H)= F. A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k⩾1 and t⩾1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.
- Sprache
- Englisch
- Identifikatoren
- ISSN: 0020-0190eISSN: 1872-6119DOI: 10.1016/S0020-0190(02)00267-3Titel-ID: cdi_proquest_journals_237281351
- Format
- –
- Schlagworte
- Algorithms, Combinatorics, Combinatorics. Ordered structures, Exact sciences and technology, Formula homomorphism, General logic, Graph theory, Logic and foundations, Mathematical logic, foundations, set theory, Mathematics, Minimal unsatisfiability, Propositional Logic, Sciences and techniques of general use, Studies