Learning Horn definitions: Theory and an application to planning

A Horn definition is a set of Horn clauses with the same predicate in all h ead literals. In this paper, we consider learning non-recursive, first-orde r Horn definitions from entailment. We show that this class is exactly lear nable from equivalence and membership queries. It follows then that this cl ass is PAC learnable using examples and membership queries. Finally, we app ly our results to learning control knowledge for efficient planning in the form of goal-decomposition rules.