Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10320289 | Artificial Intelligence | 2005 | 30 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Paolo Liberatore,