Note that the revised algorithm does not include a test for cost preserving permutations of blocks in di erent orderings (e pressed in  orollar   ), because of the highe pense of such a test.

The revised algorithm described above contains manipulations of blocks. or this pur pose, we need an eas and e cient wa to detect blocks in orderings. ince we do not permit block violation (b    orollar   ), we can unite all the subgoals of a ma  block into one entit , and treat it as an ordinar subgoal. The procedure of oining subgoals into blocks is called folding, and the resulting se  uence of ma   blocks    a folded sequence.

fter subgoals are folded into a block, there is no need to unfold this block back to separate subgoals on upper levels of the tree, these subgoals will again be  oined into a block, unless the block is violated. The unfolding operation is carried out onl  once before returning the cheapest ordering of the set (of the root node). The candidate sets of the nodes are now defined as sets of folded orderings.

s was alread stated, new blocks can onl be created in the candidates of nodes, w hen the binder is added as the first element of the ordering, if the value of the binder is greater than the value of the first ma block of the child pro ection. Therefore, in the revised algorithm we onl build new blocks that start from the binder the ma blocks in the rest of the ordering remain from the child s candidate. irst we tr to make a block out of the binder and the first ma block of the child s candidate. If the are cn ordered, we stop the folding. If the are cn inverted, we unite them into a larger block, and tr to unite it with the second ma  block of the child s candidate, and so on. The produced folded ordering contains onl ma imal blocks the first block is ma imal, since we could not e pand it further to the right, and the other blocks are ma imal, since the  were ma imal in the child s candidate.

emma 7 states that an ordering whose leading ma  block has a cheaper permutation is contradicting. ne wa to detect such a block is to e haustivel test all its permu tations, computing and companng their costs. This procedure is ver e pensive. Instead, in our revised algorithm we emplo the ad acenc restriction test (   uation ). The test is applied to ever pair of ad acent subgoals of a block, and if some ad acent pair has a cheaper transposition, then the whole block has a cheaper permutation, b emma 1. ince blocks are created b  concatenation of smaller blocks, it su  ces to test the ad acenc  restriction onl at the points where blocks are oined (for other ad acent pairs of subgoals, the tests were performed on the lower levels, when smaller blocks were formed). The ad acenc  re striction test does not guarantee detection of all not cheapest permutations (as was shown ample ), but it detects such blocks in man  cases, and works in linear time.

i n The final version of the DAC subgoal ordering algorithm is presented in   igure 1 .  The complete correctness proof of  lgorithm  is found in   ppendi

## 4.7  Sample Run And Comparison Of Ordering Algorithms

e illustrate the work of the DAC algorithm, using the subgoal set shown in  igure  ,
) (  ) (  ) .  fter proving  (  ), (  ) or  (  ), we can assume that bound.  et the control values for the subgoals be as shown in Table  . The column  (
contains control values for the subgoal (  ) when .

is not  et bound b  the preceding subgoals (i.e., the binding set does not contain  (  ) or  (  )).  The column  (