METEORS: High Performance Theorem Provers Using Model Elimination
Abstract
Historically, depth-first (linear) resolution procedures have not fared well in proving deeper theorems relative to breadth-first resolution provers of various types, primarily because of the search redundancy problem. However, we can now demonstrate that the Model Eliminator (ME) procedure, a linear-input resolution-like procedure, may be a superior approach for certain types of problems (generally non-Horn problems). There is a conjunction of reasons why the METEOR provers presently appear so effective. The reasons are: the inherent speed advantage of linear input systems, the sophistication of the WAM architecture in exploiting this advantage, a program written in the language C using tight coding and effective data structures, the speed of the platforms on which they run, and the successful use of different search strategies. We explore single processor and parallel processor implementations of ME using different versions of interactive depth-first search. Among the theorems we prove are variants of a problem in calculus for which this ME theorem prover is presently the only uniform first-order proof procedure realization that has succeeded in proving these variants.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1991
- Accession Number
- ADA244405
Entities
People
- D. W. Loveland
- O. L. Astrachan
Organizations
- Duke University