We report results about the redundancy of formulae in 2CNF form. In particular, we give a slight improvement over the trivial redundancy algorithm and give some complexity results about some problems related to finding Irredundant Equivalent Subsets (i.e.s.) of 2CNF formulae. The problems of checking whether a 2CNF formula has a unique i.e.s. and checking whether a clause in is all its i.e.s.'s are polynomial. Checking whether a 2CNF formula has an i.e.s. of a given size and checking whether a clause is in some i.e.s.'s of a 2CNF formula are polynomial or NP-complete depending on whether the formula is cyclic. Some results about Horn formulae are also reported. © 2007 Elsevier B.V. All rights reserved.
Redundancy in logic II: 2CNF and Horn propositional formulae / Liberatore, Paolo. - In: ARTIFICIAL INTELLIGENCE. - ISSN 0004-3702. - STAMPA. - 172:2-3(2008), pp. 265-299. [10.1016/j.artint.2007.06.003]
Redundancy in logic II: 2CNF and Horn propositional formulae
LIBERATORE, Paolo
2008
Abstract
We report results about the redundancy of formulae in 2CNF form. In particular, we give a slight improvement over the trivial redundancy algorithm and give some complexity results about some problems related to finding Irredundant Equivalent Subsets (i.e.s.) of 2CNF formulae. The problems of checking whether a 2CNF formula has a unique i.e.s. and checking whether a clause in is all its i.e.s.'s are polynomial. Checking whether a 2CNF formula has an i.e.s. of a given size and checking whether a clause is in some i.e.s.'s of a 2CNF formula are polynomial or NP-complete depending on whether the formula is cyclic. Some results about Horn formulae are also reported. © 2007 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
VE_2008_11573-124767.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
417.23 kB
Formato
Adobe PDF
|
417.23 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.