Avoiding Non-termination when Learning Logical Programs: A Case Study with FOIL and FOCL

Many systems that learn logic programs from examples adopt θ-subsumption as model of generalization and refer to Plotkin's framework in order to define their search space. However, they seldom take into account the fact that the lattice defined by Plotkin is a set of equivalence classes rather than simple clauses. This may lead to non-terminating learning processes, since the search gets stuck within an equivalence class, which contains an infinite number of clauses. In the paper, we present a task that cannot be solved by two well-known systems that learn logic programs, FOIL and FOCL. The failure is explained on the ground of the previous consideration about the search space. This task can be solved by adopting a weaker, but more mechanizable and manageable, model of generalization, called θ-subsumption under object identity (θ OI-subsumption). Such a solution has been implemented in a new version of FOCL, called FOCL-OI.