Extrinsic heuristic

Example 4-7 For the compressll problem, the extrinsic heuristic leads towards selecting has one plateau less than as well-founded relation over the type of L, because it reflects the structure of the C parameter. But we retain the well-founded relation suggested by the Intrinsic Heuristic for the remainder of this section, and come back to this decision in Section 5.2.1. 

None of these two heuristics is superior to the other. In the sequel, when talking about a logic algorithm LA(r), we sometimes write LA r-int-X), or LA r-ext-X), to show that X was selected as induction parameter, and that the intrinsic (respectively extrinsic) heuristic was applied. Again, the predicate defined by LA(r-/>u-X) still is r, and not r-int-X. 

Let s first reconsider Step 2 (Selection of a Well-Founded Relation), and follow the Extrinsic Heuristic when selecting a well-founded relation over the type of the induction parameter L. This means that we want to decompose L into something smaller in a way reflecting the structure of parameter C. Every element of C represents a summary of a plateau of L, so the idea is to decompose L by extracting its first maximal plateau as head of L, and the corresponding suffix as tail of L. This decomposition is non-trivial, but considerably facilitates the rest of the construction. Step 3 is unaffected by this decision, and after Step 4, the result is ... 

An intrinsic decomposition reflects a well-founded relation selected via the Intrinsic Heuristic, and an extrinsic or logarithmic decomposition reflects a well-founded relation selected via the Extrinsic Heuristic (see Chapter 4). Sample classifications are given below. 

How to invent or reuse appropriate predicates How to implement " invented predicates The combination of partial results often is a full-scale problem by itself, as illustrated by the logic algorithms for compress (induction on C), permutation , and sort . The same holds for a decomposition following the Extrinsic Heuristic. This is known as the predicate invention problem. 

An intrinsic decomposition reflects a well-founded relation selected via the Intrinsic Heuristic (Heuristic 4-3), and an extrinsic or logarithmic decomposition reflects a well-founded relation selected via the Extrinsic Heuristic (Heuristic 4-4). The selection of a strategy is a high-level decision that may significantly affect the complexity of the resulting algorithm (but probably not its existence). A reasonable implementation of this synthesis mechanism would accept a preference hint from the specifier. 

---