
| The program: a1(c1). b   | a1(X).   |    |
|--------------------------|----------|----|
| a1(c1).                  | b        | d. |
| a2(c1).                  | d.       |    |
| a2(c1). a2(c2)           | a1(c2).  |    |

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Cost(b; a1(X); a2(X)) = 5 + 32 + 323 = 29 Cost(b; a2(X); a1(X)) = 5 + 35 + 322 = 32 Cost(a1(X); b; a2(X)) = 2 + 25 + 233 = 30 Cost(a1(X); a2(X); b) = 2 + 23 + 225 = 28 Cost(a2(X); b; a1(X)) = 5 + 25 + 232 = 27 Cost(a2(X); a1(X); b) = 5 + 22 + 225 = 29

| Cost(d; a1(X); a2(X)) = 1 + 12 + 123 = 9 Cost(d; a2(X); a1(X)) = 1 + 15 + 122 = 10 Cost(a1(X); d; a2(X)) = 2 + 21 + 213 = 10 Cost(a1(X); a2(X); d) = 2 + 23 + 221 = 12 Cost(a2(X); d; a1(X)) = 5 + 21 + 212 = 11 Cost(a2(X); a1(X); d) = 5 + 22 + 221 = 13   |
|---|

![0_image_2.png](0_image_2.png)

Figure 9: We show a small program and the control values it denes. Then we compute costs of all permutations of the sets b; a1(X); a2(X) and d; a1(X); a2(X) . Dierent orderings of a1(X); a2(X) are consistent with minimal orderings of these sets.

Since, unlike the case of Merge Sort, we cannot always identify a single ordering of the subset consistent with a minimal ordering of the whole set, our algorithm will deal with sets of candidate orderings. Our requirement from such a set is that it contain at least one local ordering consistent with a global minimal ordering, if such a local ordering exists

(\local" ordering is an ordering of the set of the node, \global" ordering is an ordering of the set of the root). Such a set will be called valid. The following denition denes valid sets formally, together with several other concepts.

Denition: Let 0 be a set of subgoals and N be a node in the divisibility tree of 0.

Recall that ( ) denotes the set of all permutations of .

1. O S ( 0) is binder-consistent with O N ( (N )) (denoted B C N (O N O S)), if they are consistent, and all subgoals of (N ) appear in O S before all subgoals of O N

B C N (O N O S) () 9O B ( (N )) : C ons (O B O N O S)
O S ( 0) is binder-consistent with the node N (denoted B C N (O S )), if it is binderconsistent with some ordering of (N ):

$$N\left(\begin{array}{c c c c c}{{s}}&{{}}&{{}}&{{}}&{{\exists}}&{{}}&{{N}}&{{}}&{{}}&{{\left(\begin{array}{c c c c c}{{}}&{{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{}}&{{}}&{{}}\end{array}\right)}}&{{}}&{{}}&{{N\left(\begin{array}{c c c c c}{{}}&{{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{}}&{{}}&{{}}\end{array}\right)}}\end{array}\right)$$

2. O N ( (N )) is min-consistent with O S ( 0) (denoted M C N ;S0 (O N O S)), if they are binder-consistent, and O S is minimal:

$$N,\mathcal{S}_{0}\left(\begin{array}{c c c}{{}}&{{}}&{{}}\\ {{}}&{{N}}&{{}}\end{array}\right)$$

M C N ;S0(O N O S ) () B C N (O N O S) M in (O S 0)
O N ( (N )) is min-consistent (denoted M C N ;S0 (O N )), if it is min-consistent with some ordering of 0

$N$,${\cal S}_{0}\left(\begin{array}{c}\\ N\end{array}\right)$$\exists$$S$$\left(\begin{array}{c}\\ 0\end{array}\right)$$N$,${\cal S}_{0}\left(\begin{array}{c}\\ N\end{array}\right)$

$58\frac{1}{2}$