Second-Order Matching Modulo Evaluation: A Technique for Reusing Proofs

Abstract

Abstract 1 We investigate the improvement of theorem provers by reusing previously computed proofs. A proof of a conjecture is generalized by replacing function symbols with function variables. This yields a schematic proof of a schematic conjecture which is instantiated subsequently for obtaining proofs of new, similar conjectures. Our reuse method requires solving so-called free function variables, i.e. variables which cannot be instantiated by matching the schematic conjecture with a new conjecture. We develop an algorithm for solving free function variables by combining the techniques of symbolic evaluation and second-order matching. Heuristicsfor controlling the algorithm are presented, and several examples demonstrate their usefulness. We also show how our reuse proposal supports the discovery of useful lemmata. 1