The Narkgraf Karl

IJCAI 1981

Sure, here's a blog-style summary of the paper "The Markgraf Karl Refutation Procedure (Fall 1981)":

TL;DR

This paper introduces the Markgraf Karl Refutation Procedure (MKRP), a theorem prover designed to overcome the limitations of traditional systems by incorporating domain-specific knowledge and heuristics. The goal is to achieve a more "active" and directed proof search, leading to significantly improved performance and the ability to prove more complex theorems.

What Problem Does This Paper Address?

Automated theorem proving (ATP) systems have historically struggled with performance issues, largely due to their reliance on brute-force search through vast, irrelevant search spaces. This paper argues that the weakness of current ATP systems compared to human mathematicians stems from a lack of rich mathematical and extramathematical knowledge. Traditional approaches focused on refining search strategies or using different logics, but the authors believe the key lies in explicitly representing and utilizing knowledge about the subject matter and proof-finding strategies.

Methods

The MKRP system is designed with a three-part architecture:

  • Supervisor: This module generates overall proof proposals, invokes relevant knowledge, and transforms this information into technical instructions for the Logic Engine. It's the "brain" of the system, aiming for directed behavior.
  • Logic Engine: This is a traditional theorem prover based on Kowalski's connection graph proof procedure. It's augmented with components to enhance its strength, including a sophisticated Deletion-Module that leverages the snowball effect of removing redundant clauses.
  • Data Banks: These store factual knowledge of the specific mathematical field (definitions, axioms, proved theorems, lemmas), augmented with local knowledge about their potential use.

A key innovation is the extensive use of heuristics to guide the search. These heuristics are derived from both human experiments and analysis of the system's own proof attempts. They are local, syntactical pieces of information about the graph or resolvent, used to assign a "priority value" to links (potential resolution steps). The system also incorporates a Terminator Module that acts as a fast, limited-depth prover and a more sophisticated n-level look-ahead technique to detect proofs within a predefined complexity bound, which is a significant source of its performance improvement.

Datasets

The paper mentions testing the system on examples from the ATP literature, specifically citing:

  • Examples from a comparative study by Wilson and Minker [WM76], which involved 152 examples.
  • Examples from the work of Boyer and Moore [BM78].

The authors also state their intention to test on examples from [KRYKU72] and [MOW76]. The system is designed to handle theorems from a standard mathematical textbook, with a focus on automata theory.

Key Insights and Ideas

  • Knowledge is King: The core idea is that explicit representation and utilization of domain-specific knowledge and proof strategies are crucial for overcoming the performance limitations of traditional ATP systems.
  • Active vs. Passive Search: The goal is to move from "passive" combinatorial search to an "active" and directed search, guided by intelligent heuristics.
  • The Power of Deletion: The Deletion-Module, by aggressively removing redundant clauses, creates a "snowball effect" that dramatically reduces the search space and improves performance.
  • Heuristics as Guides: Local, syntactical heuristics, derived from both human intuition and system analysis, are essential for guiding the search effectively.
  • Terminator for Efficiency: A multi-level terminator heuristic helps to quickly identify simple proofs and avoid getting bogged down in complex searches.

Key Results

The paper presents performance statistics in Figure 5, comparing the Markgraf Karl Procedure (MKRP) to other proof procedures from the Maryland study [WM76].

  • Reduced Clauses: For the tested examples, MKRP generated significantly fewer clauses in the proof compared to the best and worst procedures from the Maryland study. For instance, for the LS-35 axiom set, MKRP generated 9 clauses, while the best Maryland procedure generated 335 and the worst 1521.
  • Improved Performance: The results are presented as representative and uniformly favorable, supporting the claims of improved performance and reduced redundancy.
  • Efficiency in Handling Large Graphs: The system demonstrated an ability to handle a challenging example (Andrews' challenge) that initially generated thousands of links, reducing it to a manageable graph of around 50 links, proving it within a few steps.

Limitations and Future Work

  • Current Limitations: The authors acknowledge that the system is not yet fully implemented. Specifically, the Supervisor (Proof Generator and Technical Assistant) is still under development. The system also has limitations in handling induction and equality axioms, where it is outperformed by specialized systems.
  • Future Work: The paper explicitly mentions ongoing development of the Supervisor modules. Future work will also focus on implementing paramodulated connection graphs, a more refined monitoring system, and improved induction capabilities. The authors believe that once these modules are operational, traditional theorem provers will no longer be competitive. They also suggest that future TP systems will need to be evaluated not just on search space but on total time and space resources.

Summary updated

BibTeX
@inproceedings{1981narkgraf,
  title = {{The Narkgraf Karl}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1981},
}
Figure