Introduction
In the field of automated theorem proving, the resolution principle stands as a cornerstone of logical deduction. However, general-purpose resolution often falters when faced with specific domain knowledge, such as mathematical orderings or taxonomic hierarchies. In his seminal work, Mark E. Stickel introduced theory resolution, a framework designed to embed these "nonequational" theories directly into the inference engine. By "building in" the logic of specific domains, Stickel demonstrated how to bypass the exponential search space explosion that typically plagues general-purpose provers.
The Problem: The Axiom Bottleneck
During the early 1980s, the primary challenge in automated reasoning was the inefficiency of handling axioms that define relations like transitivity (e.g., if $a < b$ and $b < c$, then $a < c$) or taxonomic inheritance (e.g., "All Men are Persons"). When these axioms are treated as standard clauses, a resolution-based prover often enters a cycle of deriving numerous, technically correct but practically useless consequences. This "infinite loop" of derivations causes the search space to expand uncontrollably, making it nearly impossible to find a proof for complex problems.
While researchers had previously developed methods to "build in" equality (equational theories), a generalized approach for nonequational logic—essential for Artificial Intelligence and knowledge representation—was missing. Stickel’s theory resolution was proposed to fill this gap.
The Theory Resolution Framework
Stickel’s approach moves the burden of reasoning from the general search procedure to specialized "theory-aware" mechanisms. He proposed two primary variants of this framework:
1. Total Theory Resolution
Total theory resolution utilizes a "black box" decision procedure to evaluate a set of clauses. This procedure determines if a collection of literals is collectively inconsistent within a specific theory. If an inconsistency is found, the prover generates a new clause that represents the logical conclusion of that inconsistency, effectively "skipping" the intermediate steps that the theory handled internally.
2. Partial Theory Resolution
Partial theory resolution offers a more granular and flexible approach. Instead of evaluating an entire set of clauses, it examines pairs of literals. If the literals are inconsistent under certain conditions, the system generates a residue. A residue is a new clause containing the remaining parts of the original clauses plus the negated conditions required to trigger the inconsistency. This allows the theorem prover to collaborate with specialized knowledge representation (KR) systems; the KR system identifies the conflict and informs the main prover of the remaining logical "conditions."
Key Insights: Axiom Hiding and Residues
The core innovation of theory resolution is axiom hiding. By integrating the theory's logic into the matching and resolution operations, the theory's axioms (such as transitivity) never actually appear as clauses in the search space. This drastically reduces the number of resolution steps required to reach a conclusion.
Furthermore, Stickel’s framework provides a unified view of automated deduction. He demonstrated that several existing specialized techniques, such as paramodulation for equality or Z-resolution, are actually specific instances of the broader theory resolution framework. This unification allowed for a more systematic study of how different logical theories could be integrated into a single prover.
Evaluation and Applications
As a theoretical contribution, the paper evaluates these concepts through illustrative examples rather than modern benchmarks. Stickel focused on two primary theories:
- ORD: A theory of partial ordering used for reasoning about inequalities ($<$ and $>$).
- TAX: A taxonomic hierarchy theory used for reasoning about "is-a" relationships and property inheritance.
The paper provides formal proofs that theory resolution is complete for ground clauses. This ensures that if a logical contradiction exists, the system is guaranteed to find it, even with the theory "built in." Stickel also outlined a roadmap for how the "TBox" (terminological component) and "ABox" (assertional component) of KR systems like KRYPTON could interact through this logical framework.
Limitations and Future Directions
Despite its power, theory resolution faces several challenges:
- Complexity of Decision Procedures: Total theory resolution requires robust procedures capable of handling disjunctions, which were computationally expensive for many AI systems of the era.
- Overlapping Theories: Reasoning across multiple, overlapping theories (e.g., a system combining equality with partial ordering) remains a complex problem.
- Implementation Tuning: At the time, Stickel was implementing these methods within the KLAUS natural-language-understanding system. A significant open question remained regarding how to "tune" residue generation to prevent the search space from being cluttered with unnecessary clauses.
Conclusion
Stickel’s theory resolution represented a significant leap forward in making automated theorem provers more practical for AI applications. By treating domain-specific axioms as part of the inference rule rather than part of the data, he provided a blueprint for more efficient, specialized reasoning engines that could handle the complexities of real-world knowledge.
Summary updated