And-Or Graphs Applied to RUE Resolution

TL;DR

This paper tackles the non-termination issue in RUE (Resolution by Unification and Equality) resolution's viability test, a crucial component for deciding disagreement sets. By applying the theory of And-Or graphs, the authors propose a method to guarantee termination and improve the efficiency of RUE refutations, making them more succinct and robust.

What Problem Does This Paper Address?

Resolution is a fundamental inference rule in automated theorem proving. Standard resolution works well for propositional logic but struggles with first-order logic, especially when dealing with equality. RUE resolution extends binary resolution by incorporating equality axioms directly into the resolution process, aiming to eliminate the need for explicit equality axioms in refutations. A key part of RUE resolution is the "viability test," which helps decide which disagreement sets are useful for refutation. However, this viability test can, in some cases, lead to non-terminating computations. This paper addresses this critical non-termination problem, which undermines the strong form of RUE resolution.

Methods

The core of this paper's contribution lies in applying the theory of And-Or graphs to the viability test in RUE resolution.

  • And-Or Graphs: These graphs represent problems as a combination of "AND" nodes (where all subproblems must be solved) and "OR" nodes (where any one subproblem needs to be solved). They are used to decompose problems into smaller, manageable parts.
  • Viability Test as an And-Or Graph: The authors propose constructing an And-Or graph where nodes represent aspects of the viability test. This graph structure allows for a systematic analysis of the test's execution.
  • Implicant Algorithm: They leverage a standard algorithm for finding implicants (solutions) in And-Or graphs. This algorithm, when applied to the viability graph, can determine if a solution exists.
  • Guaranteed Termination: By using the implicant algorithm on the And-Or graph representation of the viability test, the authors show that the process is guaranteed to terminate. Cycles in the graph are handled by the algorithm, preventing infinite loops.
  • RUE Unifier and Viability: The paper connects the concept of a viable disagreement set to the definition of the RUE unifier, ensuring that only "useful" substitutions are considered.

Datasets

Not discussed in the paper. The paper focuses on theoretical advancements and algorithmic improvements rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Viability Test Non-Termination is Solvable: The most significant insight is that the non-termination problem of the viability test, previously a major hurdle for RUE resolution, can be overcome by reframing it as an And-Or graph problem.
  • And-Or Graphs as a Powerful Analysis Tool: The paper demonstrates the utility of And-Or graphs beyond simple problem decomposition, showing their application in analyzing the termination properties of complex inference procedures.
  • Circularity in Viability is Manageable: The presence of cycles in the viability test (leading to non-termination) is directly mapped to cycles in the And-Or graph, which the implicant algorithm can effectively handle.
  • Succinctness of RUE Refutations: The paper reiterates that RUE refutations are typically shorter than those using explicit equality axioms, and this work makes that advantage more reliable.

Key Results

  • Guaranteed Termination of Viability Test: The primary result is the demonstration that applying the And-Or graph framework and its implicant algorithm to the viability test ensures termination.
  • Improved Robustness of RUE Resolution: By solving the non-termination issue, the strong form of RUE resolution becomes more robust and practically applicable.
  • Theoretical Foundation for RUE Unifier: The paper solidifies the theoretical underpinnings of the RUE unifier by providing a guaranteed termination mechanism for its definition.

Limitations and Future Work

  • Formalization of And-Or Graph for Viability: The authors mention that a strict formalization of the And-Or graph applied to viability, defining different node types (inequality, argument, unification, function-matching, disagreement set), will be presented in a future paper.
  • Empirical Evaluation: While the theoretical benefits are clear, the paper doesn't present empirical results or benchmarks comparing the performance of the terminated RUE resolution against other methods. This would be a natural next step.
  • Complexity Analysis: A detailed complexity analysis of the proposed approach, especially in terms of the size of the generated And-Or graphs and the implicant algorithm's performance, is not provided.

Summary updated

BibTeX
@inproceedings{1989or,
  title = {{And-Or Graphs Applied to RUE Resolution}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure