Rippling: Meta-level Guidance for Mathematical Reasoning

4.5: Structure-preserving rules

4.5 Structure-preserving rules

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.

Definition 4

A structure preserving rule is given by a pair of terms l and r in , written as l r, where

  1. erase( l) ? erase ( r) ? , and

  2. 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...

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: Tube Bending Tooling
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.