Sample PAC-learnability in model inference

In this article, PAC-learning theory is applied to model inference, which concerns the problem of inferring theories from facts in first order logic. It is argued that uniform sample PAC-learnability cannot be expected with most of the ‘interesting’ model classes. Polynomial sample learnability can only be accomplished in classes of programs having a fixed maximum number of clauses. We have proved that the class of context free programs in a fixed maximum number of clauses with a fixed maximum number of literals is learnable from a polynomial number of examples. This is also proved for a more general class of programs.