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.
2005
computational complexity; formula minimization; propositional logic; redundancy
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/125448
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 82
  • ???jsp.display-item.citation.isi??? 64
social impact