aedt, 199 ). There, logic programs are automaticall induced b  learning.  
e uch learning algorithms are commonl built with the aim of speeding up the induction process wit hout considering the e cienc of resulting programs.

The goal of the research described in this paper is to design algorithms that automat icall find e cient orderings of subgoal se uences. everal researchers have e plored the problem of automatic reordering of subgoals in logic programs (   arren, 19  1  Naish, 19    b enesereth, 19 Natara an, 19 7 Narkovitch N cott, 19 9). The general sub mit h www. I was all the state of llman Vardi, 19 ).

mith and enesereth (19 ) and arkovitch and cott (19 9) present search algorithms for finding optimal orderings. These algorithms are general and carr e  ponential costs for nnntrivial sets of subgoals. Natara an (19 7) describes an e cient algorithm for the special case where subgoals in the set do not share free variables.

In this paper we present a novel algorithm for subgoal ordering, e call two subgoals that share a free variable dependent. nlike Natara an s approach, which can onl handle ssseens that are completel independent, our algorithm can deal with an subgoal set, while making ma imal use of the e isting dependencies for acceleration of the ordering process. In the worst case the algorithm like that of mith and enesereth is e ponential.

till, in most practical cases, our algorithm e  ploits subgoal dependencies  and finds optimal orderings in pol  nomial time.

e start with an anal sis of the ordering problem and demonstrate its importance through e amples.    e then show how to compute the cost of a given ordering based on the cost and the number of solutions of the individual subgoals. e describe the algorithm of Natara an and the algorithm of mith and enesereth and show how the two can be combined into an algorithm that is more e  cient and general than each of the two.

s how drawbacks of the combined algorithm and introduce the new algorithm, which avoids these drawbacks. e call it the Divide-and-Conquer algorithm (dac algorithm).

e prove the correctness of the algorithm, discuss its comple it and compare it to the combined agorithm. The DAC algorithm assumes knowledge of the cost and the number of solutions of the subgoals. This knowledge can be obtained b  machine learning techni ues such as those emplo ed b arkovitch and cott (1999). inall , we test the utilit of our algorithm b running a set of e  penments on artificial and real domains.

The DAC algorithm for subgoal ordering can be combined with man  e isting methods in logic programming, such as program transformation, compilation, termination control, correctness verification, and others. e discuss the possibilities of such combinations in the concluding section.

ection states the ordering problem. ection describes e isting ordering algorithms and their combination.   ection   presents the new algorithm.   ection   discusses the ac uisition of the control knowledge. ection contains e perimental results. ection 7 contains a discussion of practical issues, companson with other works and conclusions.

## 2. Background: Automatic Ordering Of Subgoals

e start b  describing the conventions and assumptions accepted in this paper. Then we demonstrate the importance of subgoal ordering and discuss its validit . inall , we present a classification of ordering methods and discuss related work.