Introduction: The Challenge of Equality in Automated Reasoning
In automated theorem proving, handling equality (e.g., $a=b$) is a significant hurdle. Traditional resolution methods often require a vast set of equality axioms, which exponentially increases the search space and degrades performance. Resolution by Unification and Equality (RUE) was developed to address this by integrating equality directly into the resolution process.
Instead of requiring perfect matches between terms, RUE utilizes "disagreement sets." When terms do not unify, RUE generates inequalities that must be resolved later in the proof. To maintain efficiency, RUE employs a viability test to prune the search space by determining which inequalities are worth pursuing.
However, the original formulation of the viability test was recursive and prone to infinite loops in cases where terms cycled back on themselves. This paper presents a mathematical framework to resolve this non-termination issue by modeling the test as an And-Or graph.
Methodology: From Recursion to Graph Topology
The core innovation lies in bridging resolution theory with graph theory. By representing the recursive viability test as an And-Or graph, the authors transform a potential infinite recursion into a finite traversal problem.
1. And-Or Expansions
The graph uses two types of logical expansions:
- And-Expansion: Represents a conjunctive requirement. For example, to prove that two complex terms match, the system must prove that all their corresponding arguments match.
- Or-Expansion: Represents a disjunctive choice. An inequality is considered viable if it can match any existing equality literal within the database.
2. The Implicant Algorithm and Cycle Detection
The authors adapt the Implicant Algorithm (Chang and Slagle, 1971) to systematically expand nodes. A critical component is subsumption, which discards redundant, complex solutions in favor of simpler ones.
Crucially, the graph model allows for cycle detection. When a recursive call encounters a duplicate sub-problem, the system "arcs back" to an existing node rather than creating a new one. This ensures that the search space remains finite.
Key Insights
- Recursion as a Topology: The "halting problem" of the viability test is reframed as a graph topology issue. Mapping logic to a graph allows the use of standard cycle-breaking techniques to guarantee termination.
- Theoretical Finiteness: Since any set of logical clauses contains a finite number of terms and subterms, the resulting And-Or graph is guaranteed to be finite, providing a theoretical "safety net."
- Optimization through RUE: RUE resolution is not just a fix for equality; it is an optimization. RUE refutations are often less than half the length of those produced by standard methods using equality axioms.
Results and Conclusion
The primary result of this work is a proof-of-concept demonstrating that the Implicant Algorithm, when applied to the viability test, consistently converges. Even in the presence of cycles, the algorithm reaches either a set of solutions or an "empty formula" indicating a dead end.
By filtering out non-viable paths, the theorem prover avoids an explosion of the search space. Experimental results with this method have shown performance superior to traditional equality-handling techniques, offering a robust and efficient path forward for automated reasoning systems.
Summary updated