Polynomial-time learnability of logic programs ...

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

Authors: M.R.K. Krishna Rao and A. Sattar
Email: sattar@cit.gu.edu.au
Source: Theoretical Computer Science Vol. 268, Issue 2, 17 October 2001, pp. 179 - 198.
Abstract. In 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.