Learning First-Order Acyclic Horn Programs from Entailment

Abstract

. In this paper, we consider learning first-order Horn programs from entailment. In particular, we show that any subclass of first-order acyclic Horn programs with constant arity is exactly learnable from equivalence and entailment membership queries provided it allows a polynomial-time subsumption procedure and satisfies some closure conditions. One consequence of this is that first-order acyclic determinate Horn programs with constant arity are exactly learnable from equivalence and entailment membership queries. 1 Introduction Learning first-order Horn programs---sets of first-order Horn clauses---is an important problem in inductive logic programming with applications ranging from speedup learning to grammatical inference. We are interested in speedup learning, which concerns learning domainspecific control knowledge to alleviate the computational hardness of planning. One kind of control knowledge, which is particularly useful in many domains, is represented as goal-decomposition...