
## Validleaffilter(Conssetn)

let   Cand Set N
loop for N ConsSetN
if. N is sorted b and there is no N CandSetN which is sorted b then  Cand Set N
eturn CandSetN
ValidANDFilter(ConsSetN 
C k )
let   Cand Set N
loop for N ConsSetN
loop for    1 to let ; be the pro ection of N on ;
if and ma  blocks of  ¡ s are not violated in  N ;
and ma blocks of i s are ordered b    in  N,
and there is no N CandSetN consistent with all s, then  Cand SetN        Cand SetN
eturn CandSetN
ValidORFilter(ConsSetN)
let   Cand Set N
loop for N ConsSetN
if N does not start with a block having a cheaper permutation, and there is no cost preserving permutations in blocks,

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

then  Cand Set N
eturn CandSetN

The three filter procedures that convert a consistency set into a candidate set. Together ig ure 1 with Algorithm 5, they form a complete ordering algorithm.  The efficiency of the algorithm can be improved, as we shall see in Algorithm 6.
b . The candidate is produced b  merging  moving in parallel on the candidates of the children and e tracting ma  blocks that are minimal b If is an node, then for each candidate of its child an ordering of is created b adding the binder to the left end of the child candidate. If this results in creation of a block that has a cheaper permutation, the ordering is re ected otherwise, it is added to the candidate set. It su ces to check onl the leading ma block.