Home | Publications | CS Home

The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference


Oleg Ledeniov and Shaul Markovitch. The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference. Journal of Artificial Intelligence Research, 9:37-97 1998.


Abstract

It is common to view programs as a combination of logic and control: the logic part defines what the program must do, the control part -- how to do it. The Logic Programming paradigm was developed with the intention of separating the logic from the control. Recently, extensive research has been conducted on automatic generation of control for logic programs. Only few of these works considered the issue of automatic generation of control for improving the efficiency of logic programs. In this paper we present a novel algorithm for automatic finding of lowest-cost subgoal orderings. The algorithm works using divide-and-conquer strategy. The given set of subgoals is partitioned into smaller sets, based on co-occurrence of free variables. The subsets are ordered recursively and merged, yielding a provably optimal order. We experimentally demonstrate the utility of the algorithm by testing it in several domains, and discuss the possibilities of its cooperation with other existing methods.


Keywords: Speedup Learning
Secondary Keywords:
Online version:
Bibtex entry:
 @article{Ledeniov:1998:DCS,
  Author = {Oleg Ledeniov and Shaul Markovitch},
  Title = {The Divide-and-Conquer Subgoal-Ordering Algorithm for Speeding up Logic Inference},
  Year = {1998},
  Journal = {Journal of Artificial Intelligence Research},
  Volume = {9},
  Pages = {37--97},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Ledeniov-Markovitch-jair1998.pdf},
  Keywords = {Speedup Learning},
  Secondary-keywords = {Logic Programming, Learning to Order, Decision Trees},
  Abstract = {
    It is common to view programs as a combination of logic and
    control: the logic part defines what the program must do, the
    control part -- how to do it. The Logic Programming paradigm was
    developed with the intention of separating the logic from the
    control. Recently, extensive research has been conducted on
    automatic generation of control for logic programs. Only few of
    these works considered the issue of automatic generation of
    control for improving the efficiency of logic programs. In this
    paper we present a novel algorithm for automatic finding of
    lowest-cost subgoal orderings. The algorithm works using divide-
    and-conquer strategy. The given set of subgoals is partitioned
    into smaller sets, based on co-occurrence of free variables. The
    subsets are ordered recursively and merged, yielding a provably
    optimal order. We experimentally demonstrate the utility of the
    algorithm by testing it in several domains, and discuss the
    possibilities of its cooperation with other existing methods.
  }

  }