Generalized Unification as Background Knowledge in Learning Logic Programs

Abstract

In this paper we investigate the roles of generalized unification as background knowledge in learning logic programs. Our framework of learning is PAC-learning. We treat logic programs in which function symbols and recursions appear. We generalize the hereditary programs, which Miyano et. al have defined to investigate the learnability of elementary formal systems, by introducing generalized unification as the back-ground knowledge of the learning algorithm. As a consequence, we succeed to revise Miyano's algorithm so that it treats another class of logic programs. Our algorithm is superior to the algorithm given by Džeroski et. al in the point that it uses no queries on target predicates. We also define the size of a sample S not as the number of atoms in S , but as the number of symbols in S . This becomes possible because the evaluation of destructors in generalized unification corresponds to the use of background predicates in Džeroski's algorithm.