Skip to main content
PRL Project

Connection-Driven Inductive Theorem Proving

by Christoph Kreitz, Brigitte Pientka

In Studia Logica, vol. 69, no. 2.

  • unofficial copies PDF, PS

We present a method for integrating rippling-based rewriting into matrix-based theorem proving as a means for automating inductive specification proofs. The selection of connections in an inductive matrix proof is guided by symmetries between induction hypothesis and induction conclusion. Unification is extended by decision procedures and a rippling/reverse-rippling heuristic. Conditional substitutions are generated whenever a uniform substitution is impossible. We illustrate the integrated method by discussing several inductive proofs for the integer square root problem as well as the algorithms extracted from these proofs.

bibTex ref: KP01

cite link