Inductive Logic Programming Beyond Logical Implication

Abstract

This paper discusses the generalization of definite Horn programs beyond the ordering of logical implication. Since the seminal paper on generalization of clauses based on θ subsumption, there are various extensions in this area. Especially in inductive logic programming(ILP), people are using various methods that approximate logical implication, such as inverse resolution(IR), relative least general generalization(RLGG), and inverse implication(II), to generalize clauses. However, a program is more general than another program does not necessarily mean that the former should logically imply the latter. At least in the context of inductive synthesis of logic programs, we observe that the set inclusion ordering on the success set of logic programs is a more useful notion of generalization. In this paper, we first define an ordering between logic programs which is strictly weaker than the implication ordering. Based on this ordering, we present a set of generalization rules borrowed from unfold/fold program transformation method and ILP. We also give some strategies to apply those rules.