An Improved Filter for Literal Indexing in Resolution Systems

Lawrence J. Henschen, Shamim A. Naqvi

Introduction

In the field of automated theorem proving, specifically within resolution-based systems, the efficiency of the inference engine is heavily dependent on the speed at which it can identify candidate literals for unification or subsumption. As the set of known clauses grows, the computational cost of searching through thousands of literals becomes a significant bottleneck. This paper presents "Formula Outlines," a novel indexing technique designed to streamline this process by replacing complex list-based operations with high-speed bitwise logic.

The Limitations of FPA Indexing

Prior to the introduction of Formula Outlines, the standard approach for literal indexing involved Feature-Predicate-Argument (FPA) lists. While FPA lists provide a structured way to organize literals, they require the system to perform extensive set operations—specifically the union and intersection of multiple lists—to generate a set of potential candidates. These operations are computationally expensive and often result in a "thick" layer of overhead before the actual unification algorithm can even begin. The authors identify the need for a "flatter" indexing structure that allows for near-instantaneous filtering of incompatible literals.

The Formula Outline Method

The proposed method represents logical formulas as "Formula Outlines," which are composed of two primary byte strings:

  1. The Symbol String: This string contains the actual symbols present in the formula, such as predicates, functions, and constants.
  2. The Indicator String: This is a bitmask where a value of 1 signifies a "rigid" symbol (a constant or a function) and a value of 0 signifies a "flexible" symbol (a variable).

The Rigid-Rigid Rule

The fundamental logic of the filter is based on the "Rigid-Rigid" rule. For two formulas to be unifiable, they must possess identical symbols at every structural position where both formulas contain a rigid symbol. If Formula A contains a constant a at a specific position and Formula B contains a function f at that same position, unification is impossible. By comparing the indicator strings, the system can quickly isolate these rigid-rigid positions.

Structural Alignment and Padding

To facilitate direct comparison between strings, the authors employ a structural alignment strategy. Every symbol is treated as having a fixed maximum number of arguments ($n$). By padding the representation, the $k$-th argument of any function is guaranteed to appear at a consistent offset within the string, regardless of the overall complexity of the formula. This uniformity allows the system to treat formulas as fixed-length records for the purpose of filtering.

Bitwise Efficiency and Filtering

The primary advantage of Formula Outlines is the ability to use bitwise operators (XOR, AND, NOT) for filtering. By applying these operators to the indicator and symbol strings of two formulas, the system can immediately determine if a pair is incompatible. Because bitwise operations are among the fastest instructions executed by a CPU, this method offers a significant performance improvement over the set-based logic of FPA lists.

Furthermore, the outline method allows for "immediate access" to groups of formulas. Because the outline abstracts away specific variable names, many different formulas can share the same outline. Comparisons can be pre-computed at the outline-group level, further reducing the number of necessary operations during the search process.

Results and Memory Considerations

The authors demonstrate that the outline method provides a powerful filter that can discard incompatible pairs before the expensive unification algorithm is invoked. In terms of resource consumption, the authors estimate that storing the necessary strings and lists for a typical system would require approximately 30-40 kilobytes of memory. For the hardware available at the time of publication (circa 1980), this was considered a highly manageable footprint.

Limitations and Future Directions

Despite its efficiency, the Formula Outline method faces certain limitations:

  • Exponential Growth: The padding requirement means that the length of the strings grows exponentially with the depth of the formula, which can become wasteful for deeply nested structures.
  • Conservative Filtering: The current implementation does not distinguish between different variables (e.g., it does not track if the same variable $x$ appears in multiple positions). Consequently, the filter is conservative; it may occasionally suggest a match that is later rejected by full unification.
  • Hybrid Approaches: To mitigate the growth issue, the authors suggest a hybrid approach: using Formula Outlines for the top levels of a formula and reverting to FPA lists for deeper, sparser levels.

Conclusion

Formula Outlines represent a significant step forward in the optimization of resolution systems. By abstracting formula structure into bit-strings and leveraging the speed of bitwise arithmetic, the method provides a high-performance alternative to traditional indexing techniques, paving the way for more scalable automated theorem provers.

Summary updated

BibTeX
@inproceedings{henschen1981improved,
  author = {Lawrence J. Henschen and Shamim A. Naqvi},
  title = {{An Improved Filter for Literal Indexing in Resolution Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1981},
}
Figure