Computer Science – Artificial Intelligence
Scientific paper
2002-11-22
Computer Science
Artificial Intelligence
Extended and revised version of a paper that has been presented at ECAI 2002
Scientific paper
10.1016/j.artint.2004.11.002
A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study the problem of checking whether a CNF formula (a set of clauses) is redundant, that is, it contains clauses that can be derived from the other ones. Any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset (I.E.S.) We study the complexity of some related problems: verification, checking existence of a I.E.S. with a given size, checking necessary and possible presence of clauses in I.E.S.'s, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence.
No associations
LandOfFree
Redundancy in Logic I: CNF Propositional Formulae does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Redundancy in Logic I: CNF Propositional Formulae, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Redundancy in Logic I: CNF Propositional Formulae will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-162201