An Efficient Subsumption Algorithm for Inductive Logic Programming

In this paper we investigate the efficiency of `-- subsumption (` ` ), the basic provability relation in ILP. As D ` ` C is NP--complete even if we restrict ourselves to linked Horn clauses and fix C to contain only a small constant number of literals, we investigate in several restrictions of D. We first adapt the notion of determinate clauses used in ILP and show that `--subsumption is decidable in polynomial time if D is determinate with respect to C. Secondly, we adapt the notion of k--local Horn clauses and show that `-- subsumption is efficiently computable for some reasonably small k. We then show how these results can be combined, to give an efficient reasoning procedure for determinate k--local Horn clauses, an ILP--problem recently suggested to be polynomial predictable by Cohen (1993) by a simple counting argument. We finally outline how the `--reduction algorithm, an essential part of every lgg ILP--learning algorithm, can be improved by these ideas. 1 INTRODUCTION The..