A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study some problems related to the redundancy of a CNF formula. In particular, any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset. We study the complexity of problems related to irredundant equivalent subsets: verification, checking existence of an irredundant equivalent subset with a given size, checking necessary and possible presence of clauses in irredundant equivalent subsets, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence. © 2004 Elsevier B.V. All rights reserved.
Redundancy in logic I: CNF propositional formulae / Liberatore, Paolo. - In: ARTIFICIAL INTELLIGENCE. - ISSN 0004-3702. - STAMPA. - 163:2(2005), pp. 203-232. [10.1016/j.artint.2004.11.002]
Redundancy in logic I: CNF propositional formulae
LIBERATORE, Paolo
2005
Abstract
A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study some problems related to the redundancy of a CNF formula. In particular, any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset. We study the complexity of problems related to irredundant equivalent subsets: verification, checking existence of an irredundant equivalent subset with a given size, checking necessary and possible presence of clauses in irredundant equivalent subsets, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence. © 2004 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
VE_2005_11573-125448.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
222.9 kB
Formato
Adobe PDF
|
222.9 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.