node, and its child node corresponding to ever  binder I f is an
( ) is A, then the consistenc set of is obtained b adding binders as the first elements to the candidates of the children

$\left(\begin{array}{ccccc}\end{array}\right)$\(\left\{\begin{array}{ccccc}\
candidate set of is an set of orderings produced b removing contradicting e uivalent orderings out of the consistenc  set of   , while keeping at least and one representative for each group of e uivalent orderings

The representative for each group of $\quad\quad\quad$ is a natural order ring:  $$\begin{array}{ccccc}&(&)&(&)\\ N&(&(&)&(&)\end{array})&N,S_{0}\left(\begin{array}{c}N\\ N\end{array}\right)\\ &\left[\begin{array}{cc}\exists&N&(&)\end{array}\right.&N,S_{0}\left(\begin{array}{c}N\\ N\end{array}\right)\right]\end{array}$$  (In other words, if some ordering is re acted, it is either $\quad\quad$\(
e uivalent to some other ordering, which is not re ected.)
There are two kinds of orderings which can be removed from
(. ) while re taining its validit MC-contradicting and MC-equivalent orderings. emoval of an contradicting ordering cannot change the number of min consistent orderings in the set if e uivalent ordering, then even if it is min consistent, some other min we remove an consistent ordering is retained in the set. If there e ists a min consistent ordering of the set of the node, then its candidate set must contain a min consistent ordering, and therefore the candidate set is valid.

Note that when our algorithm treats an node, the binder of each child is alwa s placed as the first subgoal of the produced ordering of this node. n higher levels the inner order of subgoals in the ordering does not change (consistenc is preserved). Therefore, our algorithm can onl  produce binder consistent orderings.  This e plains the choice of the names "binder" and "binding set" the subgoals of  (  ) bind some common variables
( ), since the  stand to the left of them in an  global ordering that our algorithm produces. In particular, if ( ) is independent under ( ), then the subgoals of bind all the shared free variables of   (
To implement the DPart function, we can use the nion ind data structure ( ormen, ivest, 1991, hapter ), where subgoals are elements, and indivisible sets essent of the state.

are groups. In the beginning, ever subgoal constitutes a group b  itself.

henever we discover that two subgoals share a free vanable not bound b subgoals of the binding set, we unite their groups into one. To complete the procedure, we need a wa to determine which variables are bound b  the given binding set.   ection 7.1 contains a discussion of this problem and proposes some practical solutions. inall , we collect all the indivisible subgoals into a separate group. These operations can be implemented in    (      (
) amor ti ed time, where (    ) is the inverse ckermann function, which can be considered
(1)
for all values of that can appear in realistic logic programs. Thus, the whole process of finding the divisibilit partition of subgoals can be performed in ( ) average time.

The formal listing of the ordering algorithm discussed above is shown in  igure 1 .

The algonthm does not specif  e plicitl  how candidate sets are created from consis tenc sets. To complete this algonthm, we must provide the three filtenng procedures