Abstract
This paper presents a goal-directed procedure for solving equations in equational logic programming. By combining narrowing and decomposition with a novel pruning technique called "operator derivability," the proposed method efficiently handles unsatisfiable subgoals that typically cause infinite loops in traditional solvers.
Introduction
Equational logic programming aims to unify functional programming's rewriting capabilities with logic programming's variable unification. Historically, narrowing has been the primary mechanism for this unification. However, narrowing often suffers from inefficiency and non-termination on unsatisfiable goals. An alternative, decomposition, breaks equations into sub-problems but often lacks the directional guidance of functional rules.
The Goal-Directed Approach
The authors propose a procedure that simulates innermost rewriting through three key innovations:
- Oriented Goals: Equations are treated as directed reachability problems where two terms must rewrite to a common joined term.
- Directed Rules: "Decompose" and "Restructure" rules guide the search based on term structure, mimicking the execution of functional programs.
- Operator Derivability: A simplified reachability check on function symbols that acts as a high-level filter.
Operator Derivability and Pruning
The most significant contribution is the use of a simplified rewrite system $F$ derived from the original system $R$. This system $F$ tracks only the transitions between root operators, ignoring nested arguments to create a coarse but effective reachability graph.
If a function symbol $f$ cannot reach $g$ in $F$, any goal attempting to transform $f(...)$ into $g(...)$ is immediately pruned, saving significant computational resources.
Evaluation and Results
The method was evaluated using standard benchmarks such as list reversal (rev).
In cases where traditional narrowing would generate infinite failing subgoals on unsatisfiable queries, the goal-directed procedure successfully terminates. By detecting impossible operator transitions early, the system avoids the redundant computations that plague standard decomposition methods.
Conclusion
The proposed method provides a more robust and efficient framework for equational logic programming. While equation solving remains semi-decidable, the inclusion of operator derivability significantly improves the practical performance and termination properties of the solver, making it a viable approach for complex symbolic logic tasks.
Reference: Dershowitz, N., & Sivakumar, G. (1988). Goal-Directed Equation Solving. Proceedings of the Seventh National Conference on Artificial Intelligence (AAAI-88), 166–170.
Summary updated