Sh. Nienhuyscheng et R. Dewolf, LEAST GENERALIZATIONS AND GREATEST SPECIALIZATIONS OF SETS OF CLAUSES, The journal of artificial intelligence research, 4, 1996, pp. 341-363
Citations number
26
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Artificial Intelligence
The main operations in Inductive Logic Programming (ILP) are generaliz
ation and specialization, which only make sense in a generality order.
In ILP, the three most important generality orders are subsumption, i
mplication and implication relative to background knowledge. The two l
anguages used most often are languages of clauses and languages of onl
y 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 fi
nite sets of clauses in each of these six ordered sets. We survey resu
lts 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 o
ther, not necessarily function-free clauses). Secondly, we show that s
uch 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 th
e six ordered languages.