Pac-learning nondeterminate clauses
William W. Cohen · 1994
Several practical inductive logic programming systems efficiently learn "determinate" clauses of constant depth. Recently it has been shown that while nonrecursive constant-depth determinate clauses are pac-learnable, most of the obvious syntactic generalizations of this language are not pac-learnable. In this paper we introduce a new restriction on logic programs called "locality", and present two formal results. First, the language of nonrecursive clauses of constant locality is pac-learnable. Second