.png){kind=icon}
.png){kind=icon}
Return
REMOVING REDUNDANCY FROM A CLAUSE
.png){kind=icon}
PRE
AI
DOI：10.1016/0004-3702(93)90069-N.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper deals with the problem Of removing redundant literals from a given clause. We first consider condensing, a weak type of redundancy elimination. A clause is condensed if it does not subsume any proper subset of itself. It is often useful (and sometimes necessary) to replace a non-condensed clause C by a condensation, i.e., by a condensed subset of C which is subsumed by C. After studying the complexity of an existing clause condensing algorithm, we present a more efficient algorithm and provide arguments for the optimality of the new method. We prove that testing whether a given clause is condensed is co-NP-complete and show that several problems related to clause condensing belong to complexity classes that are, probably, slightly harder than NP. We also consider a stronger version of redundancy elimination: a clause C is strongly condensed iff it does not contain any proper subset C' such that C logically implies C'. We show that the problem of testing whether a clause is strongly condensed is undecidable.
Keywords:
SUBSUMPTION
COMPLEXITY
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W
Organization
No organization information available