Choosing Directions for Rules

In "expert systems" and other applications of logic programming, the issue arises of whether to use rules for forward or backward inference, i.e. whether deduction should be driven by the facts available to the program or the questions that are put to it. Often some mixture of the two is cheaper than using either mode exclusively. We show that, under two restrictive assumptions, optimal choices of directions for the rules can be made in time polynomial in the number of rules in a recursion-free logic program. If we abandon either of these restrictions, the optimal choice is NP-complete. A broad range of cost measures can be used, and can be combined with bounds on some element of the total cost.

Authors

• Richard Treitel Michael Genesereth

Keywords

No keywords are indexed for this paper.