Choosing Directions for Rules

Proceedings of the AAAI Conference on Artificial Intelligence, 5

Volume

Science

Search

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.