Polynomial-time learnability of logic programs with local variables from entailment

In this paper, we study exact learning of logic programs from entailment an d present a polynomial time algorithm to learn a rich class of logic progra ms that allow local variables and include many standard programs like appen d, merge, split, delete, member, prefix, suffix, length, reverse, append/4 on lists, tree traversal programs on binary trees and addition, multiplicat ion and exponentiation on natural numbers. Grafting a few aspects of increm ental learning (Krishna Rao, Proc. Algorithmic Learning Theory, ALT'95, Lec ture Notes in Artificial Intelligence, vol, 997, pp. 95-109. Revised versio n in Theoret. Comput. Sci. special issue on ALT'95 185 (1995) 193-213) onto the framework of teaming from entailment (Arimura, Proc. Algorithmic Learn ing Theory, ALT'97, Lecture Notes in Artificial Intelligence, vol. 1316, 19 97, pp. 432-445), we generalize the existing results to allow local variabl es, which play an important role of sideways information passing in the par adigm of logic programming. (C) 2001 Elsevier Science B.V. All rights reser ved.