William W. Cohen
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 pat-learnable, most of the obvious syntactic generalizations of this language are not pat-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, the language of nonrecursive clauses of constant locality is strictly more expressive than the language of nonrecursive determinate clauses of constant depth. Hence, constant-locality clauses are a pat-learnable generalization of constant-depth determinate clauses.