Pac-Learning Recursive Logic Programs: Efficient Algorithms
<|reference_start|>Pac-Learning Recursive Logic Programs: Efficient Algorithms: We present algorithms that learn certain classes of function-free recursive logic programs in polynomial time from equivalence queries. In particular, we show that a single k-ary recursive constant-depth determinate clause is learnable. Two-clause programs consisting of one learnable recursive clause and one constant-depth determinate non-recursive clause are also learnable, if an additional ``basecase'' oracle is assumed. These results immediately imply the pac-learnability of these classes. Although these classes of learnable recursive programs are very constrained, it is shown in a companion paper that they are maximally general, in that generalizing either class in any natural way leads to a computationally difficult learning problem. Thus, taken together with its companion paper, this paper establishes a boundary of efficient learnability for recursive logic programs.<|reference_end|>
@article{cohen1995pac-learning,
    title={Pac-Learning Recursive Logic Programs: Efficient Algorithms},
    author={W. W. Cohen},
    journal={Journal of Artificial Intelligence Research, Vol 2, (1995),
  501-539},
    year={1995},
    archivePrefix={arXiv},
    eprint={cs/9505104},
    primaryClass={cs.AI}
}