We present positive PAC-learning results for the nonmonotonic inductiv
e logic programming setting. In particular, we show that first-order r
ange-restricted clausal theories that consist of clauses with up to k
literals of size at most j each are polynomial-sample polynomial-time
PAC-learnable with one-sided error from positive examples only. In our
framework, concepts are clausal theories and examples are finite inte
rpretations. We discuss the problems encountered when learning theorie
s which only have infinite nontrivial models and propose a way to avoi
d these problems using a representation change called flattening. Fina
lly, we compare our results to PAC-learnability results for the normal
inductive logic programming setting.