
## 7.2 Relationship To Other Works

The work described in this paperis a continuation of the line of research initiated b mit h and enesereth (19 ) and continued b Natara an (19 7) and arkovitch and cott (19 9).

This line of research aims at finding the most e  cient ordering of a set of subgoals. The search for minimal cost ordering is based on cost anal sis that utili es available information about the cost and number of solutions of individual subgoals.

mith and enesereth (19 ) performed an e haustive search over the space of all permutations of the given set of subgoals, using the adjacency restriction to reduce the ssi e of the search space (  uation  ). This restriction was applied on pairs of ad acent subgoals in the global ordering of the entire set. hen applied to an independent set of ssssse subgoals in a minimal ordering must be sorted b their values. Natara an (19-7) arnved at this conclusion and presented an e  cient ordering algorithm for independent sets.

The DAC algorithm uses subgoal dependence to break the set into smaller subsets. In dependent subsets are sorted. ependent subsets are recursivel ordered, and the resulting orderings are merged using a generali ation of the ad acenc restriction that manipulates blocks of subgoals. Therefore the DAC algorithm is a generali ation of both algorithms.

uring the last decade, a significant research e ort went into static anal sis (  ) of to logic programs. There are three t  pes of that can be e  ploited b  the DAC algorithm to red uce the ordering time.

ma or part of the research deals with program termination (  e   chre  e ecorte, 199). The DAC algorithm solves the termination problem, as a special case of the e cienc opproblem (it alwa s finds a terminating ordering, if such orderings e ist).

uning learning, we set limits on the computation resources available for subgoal e ecution. If a subgoal is non terminating (in a certain mode), the learning module will associate a ver  high cost onse  uentl , the dac algorithm will not allow orderings with with this particular mode. this mode of the subgoal. Nevertheless, while the use of static termination anal sis is not mandator for a proper operation of the DAC algorithm, we can e ploit such anal sis to increase the e  cienc  of both the learning process and the ordering process.

uring learning, the limit that we set on the computation resources devoted to the e ecution of a subgoal must be high, to increase the reliabilit of the cost estimation.

owever, such a high limit can lead to a significant increase in learning time when man  subgoals are nnnnteeminating. If termination information obtained b is available, we can use it to avoid entering infinite branches of proof trees. uring ordering, termination information can serve to reduce the si e of space of orderings searched b the algorithm. If the termination information comes in the form of allowed modes ( omog i et al., 199 b), orderings that violate these modes are filtered out, as in the modified algorithm shown in   igure 1  .  If the termination information comes in the form of a partial order between subgoals, orderings that violate this partial order can be filtered out in a similar manner.

The second t  pe of research that can be combined with the DAC algorithm is correciness analysis, where the program is tested against specifications given b  the user.

The FOLON environment ( enrard e hadier, 199 ) was designed to support the methodolog  for logic program construction that aims at reconciling the declarative seman tics with an e  cient implementation (  eville, 199 ). The construction process starts with