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

AbstractIn this paper, we study exact learning of logic programs from entailment and present a polynomial time algorithm to learn a rich class of logic programs that allow local variables and include many standard programs like append, merge, split, delete, member, prefix, suffix, length, reverse, append/4 on lists, tree traversal programs on binary trees and addition, multiplication and exponentiation on natural numbers. Grafting a few aspects of incremental learning (Krishna Rao, Proc. Algorithmic Learning Theory, ALT’95, Lecture Notes in Artificial Intelligence, vol, 997, pp. 95–109. Revised version in Theoret. Comput. Sci. special issue on ALT’95 185 (1995) 193–213) onto the framework of learning from entailment (Arimura, Proc. Algorithmic Learning Theory, ALT’97, Lecture Notes in Artificial Intelligence, vol. 1316, 1997, pp. 432–445), we generalize the existing results to allow local variables, which play an important role of sideways information passing in the paradigm of logic programming