Learning function-free Horn expressions

The problem of learning universally quantified function free first order Ho rn expressions is studied. Several models of learning from equivalence and membership queries are considered, including the model where interpretation s are examples (Learning from Interpretations), the model where clauses are examples (Learning from Entailment), models where extensional or intention al background knowledge is given to the learner (as done in Inductive Logic Programming), and the model where the reasoning performance of the learner rather than identification is of interest (Learning to Reason). We present learning algorithms for all these tasks for the class of universally quant ified function free Horn expressions. The algorithms are polynomial in the number of predicate symbols in the language and the number of clauses in th e target Horn expression but exponential in the arity of predicates and the number of universally quantified variables. We also provide lower bounds f or these tasks by way of characterising the VC-dimension of this class of e xpressions. The exponential dependence on the number of variables is the ma in gap between the lower and upper bounds.