Matrix-based Inductive Theorem Proving

unofficial copies [PDF], [PS]

by Christoph Kreitz and Brigitte Pientka

International Conference TABLEAUX-2000, R. Dyckhoff (ed.), LNAI 1847, pp. 294-308, Springer-Verlag, 2000.


We present an approach to inductive theorem proving that integrates rippling-based rewriting into matrix-based logical proof search. The selection of appropriate connections in a matrix proof is guided by the symmetries between induction hypothesis and induction conclusion while unification is extended by a rippling/reverse-rippling heuristic. Conditional substitutions are generated whenever a uniform substitution is impossible. We illustrate the combined approach by discussing several inductive proofs for the integer square root problem.