Learning Logic Programs with Unary Partial Function Graph Background Knowledge (extended abstract)
Robert H. Sloan · 2003
The product homomorphism method is a combinatorial tool that can be used to develop polynomial PAC-learning algorithms in predicate logic. Using the product homomorphism method, we show that a single nonrecursive definite Horn clause is polynomially PAC-learnable if the background knowledge is a function-free extensional database over a single binary predicate and the ground atoms in the background knowledge form a unary partial function. That is, the background knowledge corresponds to a directed graph, where each node has outdegree at most 1. The proof is based on a detailed analysis of products and homomorphisms of the class of digraphs corresponding to unary partial functions.