Rippling: Meta-Level Guidance for Mathematical Reasoning
Rippling 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.
abstract additional allows annotated substitution annotated terms annotation variables applied approach automated blocked calculus called Chapter complete computes condition conjecture consider construction contain context corresponding defined definition denote described embedded equation example extend fails failure fertilization Figure formal formula function function symbols given gives goal ground Hence illustrate implement induction inductive proofs inference instance instantiated introduced kinds labeled left-hand side lemma logic mapping matching measure method move natural Note obtain patch position possible precondition presented preservation problem proof properties prove reasoning recursive relation replacement represented respect restrictions rev(t rewrite rules right-hand side rippling simple sink skeleton speculation step structure substitution subterm suggest Suppose symbol symbol occurrences techniques termination theorem tion tower transformation tree unification variables wave wave-fronts wave-hole wave-rule weakenings