Rippling: Meta-level Guidance for Mathematical Reasoning

4.7: Orders On Annotated Terms

4.7 Orders On Annotated Terms

Theorem 4 was proven for an arbitrary reduction order > on annotated terms. In this section, we give a concrete example of a reduction ordering that is useful in practice. We build our ordering in steps, starting with simply annotated terms: those whose wave-fronts have a single wave-hole. We define a measure on such terms and a corresponding order. Afterwards, we generalize this to measures and orders for terms with general (multi-hole) annotations.

4.7.1 Simple annotation

As we have seen in Figure 1.3 in Section 1.4, we can view annotated terms as decorated trees where the tree is the skeleton and the wave-fronts are boxes decorating the nodes. See, for example, the first tree in Figure 4.2, which represents . Our orders are based on assigning measures to annotations in these trees. We define orders by progressively simplifying annotated trees to capture the notion of progress during rippling that we wish to measure.


Figure 4.2: Defining a measure on annotated terms.

To begin with, since rippling is skeleton preserving, we need not account for the contents of the skeleton in our orderings. That is, we can abstract away function symbols in the skeleton, for example, mapping each to a variadic function constant * . This gives, for example, the second tree in Figure 4.2.

A further abstraction is to ignore the names of function symbols within wave-fronts and instead assign a numeric weight to each wave-front. For example, we may tally up the values...

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: Construction and Demolition Attachments
Finish!
Privacy Policy

This is embarrasing...

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