Complete Pruning Methods and a Practical Search Strategy for SOL

Hidetomo Nabeshima, Koji Iwanuma, Katsumi InoueLPAR Workshops 2008

Abstract

This paper introduces two novel pruning techniques—Extended Local Failure Caching and Skip-minimality—alongside a new search strategy called Consequence Iterative Lengthening (CIL) for the SOL (Skip Ordered Linear) tableau calculus. These methods significantly accelerate consequence finding by eliminating redundant search paths while maintaining the completeness of the calculus, even under strict constraints on the length of the results. Experimental results on the TPTP library demonstrate that these enhancements can reduce search steps by orders of magnitude.

Introduction

In traditional automated theorem proving, the primary objective is to determine the truth value of a specific statement. In contrast, consequence finding seeks to derive all "interesting" or useful statements that follow from a given set of axioms. This capability is fundamental to advanced reasoning tasks such as abduction (finding explanations), induction, and nonmonotonic reasoning.

The SOL (Skip Ordered Linear) tableau calculus is a powerful framework for consequence finding. However, it faces a massive search space challenge. While pruning is common in theorem proving, standard techniques often fail in SOL because of the unique "Skip" operation, which allows a literal to be kept as part of the resulting consequence rather than being proven. This paper addresses the inefficiency of SOL by introducing pruning methods that remain complete even when users impose limits on the length of derived consequences.

The SOL Calculus and the Skip Challenge

The core of the SOL calculus is the ability to "skip" literals. When a literal is skipped, it is not resolved away but instead becomes part of the final clause (the consequence). This creates a complex search space where a subgoal does not simply succeed or fail; it can "succeed" by being skipped, but at the cost of increasing the length of the resulting theorem.

SOL tableaux demonstrating skipped nodes and reduction operations.

As shown in Figure 1, different branches of the search tree can lead to different consequences based on which literals are skipped ($p(X)$ in $T_a$, $q(X)$ in $T_b$). Standard "local failure caching"—which prevents a solver from re-trying subgoals that have already failed—becomes incomplete in this context. A path that failed under a certain length limit might have succeeded if more literals were allowed to be skipped.

Advanced Pruning Techniques

Extended Local Failure Caching

To resolve the conflict between pruning and the "Skip" operation, the authors propose Extended Local Failure Caching. This method tracks which literals were skipped during a failed attempt to solve a subgoal. By recording these "skip sets," the system can safely prune future attempts only if they are "more general" than the failed one. This ensures that no valid, short consequences are missed while still aggressively cutting down the search tree.

Theoretical comparison of tableaux used to justify extended pruning logic.

Figure 6 illustrates the logical justification for this approach, comparing different tableaux ($T_a, T_{bs}, T_{bs}'$) to determine when a solution found in one context can be generalized to prune another branch. This formalization allows the solver to maintain mathematical completeness under length constraints.

Skip-minimality

This pruning method identifies derivations that are guaranteed to produce redundant consequences. If a derivation is on a path to producing a clause that is already "subsumed" (covered) by a simpler result found earlier, the search is halted immediately. This prevents the solver from wasting resources on consequences that provide no new information.

Consequence Iterative Lengthening (CIL)

Users typically prefer short, simple consequences over long, complex ones. To prioritize these, the authors introduce Consequence Iterative Lengthening (CIL). Similar to Depth-First Iterative Deepening (DFID), CIL repeatedly executes the search while gradually incrementing the allowed length of the consequences.

While restarting a search might seem inefficient, the exponential growth of search trees means the final iteration (with the largest length limit) dominates the total execution time. Consequently, the overhead of earlier iterations is negligible, while the benefit of finding the most useful results first is substantial.

Experimental Evaluation

The methods were implemented in SOLAR, a Java-based SOL tableau solver, and tested against satisfiable instances from the TPTP library v2.5.0. The results were dramatic:

  • Search Reduction: In the KRS005-1.p problem, the number of search steps dropped from approximately 160 million to 8.7 million with all methods enabled. Execution time fell from 438 seconds to just 36 seconds.
  • Solving Complex Problems: For the GRP123-1.005.p problem, standard methods timed out after 600 seconds. With Skip-minimality enabled, SOLAR found 65 consequences in only 4.8 seconds.
  • CIL Efficiency: CIL showed almost no performance overhead compared to standard search while successfully prioritizing shorter clauses.

Conclusion

The introduction of Extended Local Failure Caching and Skip-minimality provides a robust solution to the search space explosion in SOL tableau calculus. By combining these with the CIL search strategy, the authors have created a framework that is both efficient and complete for practical consequence finding. Future work will focus on improving clause-subsumption checking and developing specialized mechanisms for handling equality operators, which remain a challenge for current first-order logic solvers.

Summary updated

BibTeX
@inproceedings{nabeshima2008complete,
  author = {Hidetomo Nabeshima and Koji Iwanuma and Katsumi Inoue},
  title = {{Complete Pruning Methods and a Practical Search Strategy for SOL}},
  booktitle = {LPAR Workshops},
  year = {2008},
}
Figure