Avoiding Tests for Subsumption

Anavai Ramesh, Neil V. MurrayAAAI 1994

Abstract

Prime implicate discovery is a fundamental task in automated reasoning, yet it is often hindered by the computational cost of subsumption checks. This paper introduces a novel approach to speed up this process by identifying specific structural patterns—anti-links and strictly pure full blocks—within Negation Normal Form (NNF) formulas. By leveraging these patterns, the proposed method can eliminate redundant data paths without the need for expensive brute-force comparisons, significantly improving performance on complex logic benchmarks.

Introduction

In automated reasoning, finding the prime implicates of a formula—the most minimal logical consequences—is essential for tasks such as hardware verification and non-monotonic reasoning. Traditionally, this process involves converting formulas into Conjunctive Normal Form (CNF) and performing exhaustive subsumption checks to ensure that no clause is a subset of another. As the number of potential clauses grows, these checks become a massive computational bottleneck.

This paper proposes a shift from search-based redundancy detection to structural analysis. By working directly with formulas in NNF and utilizing Semantic Graphs, the authors identify topological features that guarantee redundancy, allowing for its removal without explicit comparison.

The core of the proposed approach lies in manipulating the internal structure of NNF formulas to bypass standard search limitations.

The authors represent formulas as semantic graphs, which allow for more flexible manipulation than standard clausal forms. A key structural feature identified is the anti-link, which occurs when a literal (e.g., variable $A$) appears in multiple parts of a formula.

Figure 1: A semantic graph representation of a formula in Negation Normal Form (NNF), illustrating the structural relationships between literals.

To handle these, the authors introduce the Disjunctive Anti-link Dissolvent (DADV) operator. When a literal appears in different branches of an "OR" statement (a disjunctive anti-link), the DADV operator restructures the formula to collapse these occurrences. This effectively deletes redundant paths "for free," avoiding the need for a subsumption check to prove they are unnecessary.

Strictly Pure Full Blocks

Another optimization involves identifying strictly pure full blocks—sub-formulas that share no variables with the rest of the formula. These blocks can be treated modularly; they are replaced with a dummy variable, the simplified problem is solved, and the results are mapped back. This modularity drastically reduces the search space and preserves the compact nature of the NNF representation.

Evaluation and Results

The algorithm was evaluated using benchmark logic formulas known for their difficulty, specifically Kean’s $K_{m,n}$ formulas, where the number of implicates grows exponentially relative to the input size.

Table 1: Comparison of subsumption checks required by IPIA, GEN-PI, and the proposed PI+Anti-Link method across various benchmarks.

As shown in the results, the structural approach provides a massive reduction in computational effort. For the $K_{5,4}$ benchmark, the proposed method required only 887 subsumption checks, compared to over 1.7 million for the standard Incremental Prime Implicate Algorithm (IPIA) and nearly 30,000 for the previous state-of-the-art, GEN-PI. In certain classes of formulas, such as Ngair’s formulas ($\mathcal{F}_N$), the method can find all implicates in polynomial time without performing any subsumption checks at all.

Conclusion

By focusing on the topology of logical formulas rather than exhaustive output comparisons, this research demonstrates that the primary bottleneck in prime implicate discovery can be largely bypassed. While the presence of anti-links is not guaranteed in every formula, their exploitation provides a significant speedup in complex cases. Future work may involve refining the heuristics for choosing which anti-links to dissolve first and integrating these techniques into general-purpose automated reasoning systems.

Summary updated

BibTeX
@inproceedings{ramesh1994avoiding,
  author = {Anavai Ramesh and Neil V. Murray},
  title = {{Avoiding Tests for Subsumption}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure