On Subsumption Removal and On-the-Fly CNF Simplification
- Lintao Zhang
8th International Conference on the Theory and Applications of Satisfiability Testing (SAT 2005) |
Published by Springer
CNF Boolean formulas generated from resolution or solution enumeration often have much redundancy. Efficient algorithms are needed to simplify and compact such CNF formulas. In this paper, we present a novel algorithm to maintain a subsumption-free CNF clause database by efficiently detecting and removing subsumption as the clauses are being added. We then present an algorithm that compact CNF formula further by applying resolutions to make it Decremental Resolution Free. Our experimental evaluations show that these algorithms are efficient and effective in practice.