A Rational Reconstruction and Extension of Recursion Analysis

Abstract

The focus of this paper is the technique of recursion analysis. Recursion analysis is used by the Boyer-Moore Theorem Prover to choose an appropriate induction schema and variable to prove theorems by mathematical induction. A rational reconstruction of recursion analysis is outlined, using the technique of proof plans. This rational reconstruction suggests an extension of recursion analysis which frees the induction suggestion from the forms of recursion found in the conjecture. Preliminary results are reported of the automation of this rational reconstruction and extension using the clam- Oyster system. 1 Introduction The work described in this paper is part of a project to explore the use of proof plans for the automatic guidance of mathematical proofs. In particular, we are developing proof plans for the proofs by mathematical induction that are required in the automatic synthesis of computer programs from their specifications. Given a conjecture, the clam plan form...