Rippling: Meta-Level Guidance for Mathematical ReasoningRippling is a radically new technique for the automation of mathematical reasoning. It is widely applicable whenever a goal is to be proved from one or more syntactically similar givens. It was originally developed for inductive proofs, where the goal was the induction conclusion and the givens were the induction hypotheses. It has proved to be applicable to a much wider class of tasks, from summing series via analysis to general equational reasoning. The application to induction has especially important practical implications in the building of dependable IT systems, and provides solutions to issues such as the problem of combinatorial explosion. Rippling is the first of many new search control techniques based on formula annotation; some additional annotated reasoning techniques are also described here. This systematic and comprehensive introduction to rippling, and to the wider subject of automated inductive theorem proving, will be welcomed by researchers and graduate students alike. |
Common terms and phrases
abstract level abstract proof annotated match annotated rewrite annotated substitution annotated terms annotation variables applied automated reasoning calculus Chapter computes conjecture consider context corresponding count(nodes_in(l defined delete(x denote embedded encode equation erase(t erasure even(m example exp(X F₁ fertilization first-order first-order logic flexible variables formal function symbols given goal higher-order Hutter implement induction hypothesis induction rule inductive proofs inference step instance instantiated left-hand side lemma length(X logic loop invariant meta-variables mutual recursion natural numbers notation paramodulation patch position precondition proof search prove qrev recursive definitions redex replacement reuse rev(l rev(rev(X rev(t rewrite rules rewrite step right-hand side rippling problem rippling proof rule of inference Section simply annotated sink size(r skel(t skeleton preservation source proof structural induction subterm symbol occurrences tail recursive techniques termination theorem tion unannotated unification problem universally quantified V-substitutions wave annotation wave-fronts wave-hole wave-rule weakenings