Accession Number:

ADA244405

Title:

METEORS: High Performance Theorem Provers Using Model Elimination

Descriptive Note:

Corporate Author:

DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1991-03-01

Pagination or Media Count:

31.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE