Least Generalizations and Greatest Specializations of Sets of Clauses
  The main operations in Inductive Logic Programming (ILP) are generalization
and specialization, which only make sense in a generality order. In ILP, the
three most important generality orders are subsumption, implication and
implication relative to background knowledge. The two languages used most often
are languages of clauses and languages of only Horn clauses. This gives a total
of six different ordered languages. In this paper, we give a systematic
treatment of the existence or non-existence of least generalizations and
greatest specializations of finite sets of clauses in each of these six ordered
sets. We survey results already obtained by others and also contribute some
answers of our own. Our main new results are, firstly, the existence of a
computable least generalization under implication of every finite set of
clauses containing at least one non-tautologous function-free clause (among
other, not necessarily function-free clauses). Secondly, we show that such a
least generalization need not exist under relative implication, not even if
both the set that is to be generalized and the background knowledge are
function-free. Thirdly, we give a complete discussion of existence and
non-existence of greatest specializations in each of the six ordered languages.
