Proving theorems by reuse
β Scribed by Christoph Walther; Thomas Kolbe
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 444 KB
- Volume
- 116
- Category
- Article
- ISSN
- 0004-3702
No coin nor oath required. For personal study only.
β¦ Synopsis
We investigate the improvement of theorem proving by reusing previously computed proofs. We have developed and implemented the PLAGIATOR system which proves theorems by mathematical induction with the aid of a human advisor: If a base or step formula is submitted to the system, it tries to reuse a proof of a previously verified formula. If successful, labour is saved, because the number of required user interactions is decreased. Otherwise the human advisor is called for providing a hand crafted proof for such a formula, which subsequently-after some (automated) preparation steps-is stored in the system's memory, to be in stock for future reasoning problems. Besides the potential savings of resources, the performance of the overall system is improved, because necessary lemmata might be speculated as the result of an attempt to reuse a proof. The success of the approach is based on our techniques for preparing given proofs as well as by our methods for retrieval and adaptation of reuse candidates which are promising for future proof reuses. We prove the soundness of our approach and illustrate its performance with several examples.
π SIMILAR VOLUMES
Test set induction is a goal-directed proof technique which combines the full power of explicit induction and proof by consistency. It works by computing an appropriate explicit induction scheme called a test set, to trigger the induction proof, and then applies a refutation principle using proof by
In this paper we present a theoretical basis justifying the incorporation of decidability results for a first-order theory \(T\) into an automated theorem prover for \(T\). We state rules which extend resolution using decidability results relative to \(T\) in both the ground and the non-ground case,