Learnability in inductive logic programming: some basic results and techniques
Inductive logic programming is a rapidly growing area of research that centers on the development of inductive learning algorithms for first-order definite clause theories. An obvious framework for inductive logic programming research is the study of the pac-learnability of various restricted classes of these theories. Of particular interest are theories that include recursive definite clauses. Because little work has been done within this framework, the need for initial results and techniques is great. This paper presents results about the pac-learnability of several classes of simple definite clause theories that are allowed to include a recursive clause. In so doing, the paper uses techniques that may be useful in studying the learnability of more complex classes.
