Introduction
Researchers from the University of Koblenz have developed a method to bridge the gap between high-performance automated theorem proving and the practical requirements of logic programming. Their work extends the Model Elimination (ME) proof technique to not only determine the validity of a statement but also to compute specific variable substitutions—answers—required for complex disjunctive logic programs.
The Challenge of Disjunctive Logic Programming
Standard logic programming, such as Prolog, typically utilizes Horn clauses, which are rules with a single conclusion. However, many real-world scenarios involve Disjunctive Logic Programming (DLP), where a rule can lead to multiple possible outcomes (e.g., "If it is cloudy, it might rain OR it might be overcast").
While general-purpose theorem provers can handle these disjunctions, they often act as "black boxes," proving unsatisfiability without providing concrete answers. Furthermore, they frequently require contrapositives, which can obscure the procedural intent of the original program. The goal of this research is to create a system that functions like a programming interpreter, following rules from head to tail and returning specific answers.
Methodology: From Model Elimination to Ancestry Restart
The authors' approach builds upon Model Elimination (ME), a technique that constructs a tree of goals and subgoals to find a contradiction.
Restart Model Elimination
A key variant used is Restart ME, which restricts the prover to entering a clause only through its "head" (the positive literal). If the prover reaches a positive leaf and cannot proceed, it "restarts" by copying the original goal. This behavior closely mimics a logic programming interpreter.
Ancestry Restart ME
The primary innovation presented is the Ancestry Restart variant. Instead of always restarting from the root goal, the prover can restart from any "negative ancestor" literal in the current path. This refinement allows for more efficient loop checking (regularity) and helps prune the search space significantly.
Experimental Evaluation
The researchers implemented these calculi in the PROTEIN (PROver with a Theory Extension INterface) system. They evaluated the system using Smullyan’s "Knights and Knaves" logic puzzles, which are inherently disjunctive. A primary benchmark was Problem #36 from Smullyan’s What is the Name of This Book?.
PROTEIN was compared against other prominent provers: OTTER (a resolution-style prover) and SETHEO (a connection tableau prover).
Key Results and Insights
The experiments highlighted several critical findings:
- Computing Answers is Computationally Expensive: Finding a non-trivial answer is significantly more difficult than merely proving that an answer exists.
- Preference for Definite Answers: The Ancestry Restart calculus is designed to prioritize "definite" answers (single-atom results) over indefinite disjunctions by limiting the reuse of the query clause.
- Efficiency Gains: The Ancestry Restart variant showed dramatic performance improvements. In the "Knights and Knaves" puzzle, it found a definite answer in 38.4 seconds, compared to over 2022.8 seconds for the "Plain ME" approach.
As shown in the results table, PROTEIN successfully found both indefinite and definite answers where other provers struggled. For instance, while OTTER failed to find a proof in one case within an hour, PROTEIN (using restart) succeeded in 41.4 seconds.
Conclusion
The introduction of Ancestry Restart ME in the PROTEIN system represents a significant step toward practical disjunctive logic programming. By maintaining procedural integrity and providing a mechanism for efficient answer computation, this approach offers a robust alternative to traditional black-box theorem provers. Future work will explore incorporating non-monotonic reasoning to handle even more complex programming scenarios.
Summary updated