Rippling: Meta-level Guidance for Mathematical Reasoning

As noted previously, rewrite relations are typically defined by sets of rewrite rules, s ? t ?
, where
?
. Suppose such a set
is given. We now show how to create a set of wave-rules based on
. We continue to ignore the question of termination, and simply focus on the structure preservation requirements.
A structure preserving rule is given by a pair of terms l and r in
, written as l
r, where
erase( l) ? erase ( r) ?
, and
skel( r) ? skel( l).
Given a set of rewrite rules
, let
denote the set of all structure-preserving rules based on
. Note that the first requirement tells us that since erase( l) ? erase( r) ?
, that Vars( r) ? Vars( l).
The set
is easily computed. For each s ? t ? R we must find annotated terms l, r ?
satisfying the above two requirements. Requirement (i) means that l and r correspond to s and t with additional annotations (i.e., wave-fronts and wave-holes). As explained in Section 4.3.1, there are exponentially many possible ways to annotate s and t. Let A s and A t be the sets containing these annotations. Then, to satisfy requirement (ii) we...