COMPLETENESS AND PROPERNESS OF REFINEMENT OPERATORS IN INDUCTIVE LOGIC PROGRAMMING

Within Inductive Logic Programming, refinement operators compute a set of specializations or generalizations of a clause. They are applied i n model inference algorithms to search in a quasi-ordered set for clau ses of a logical theory that consistently describes an unknown concept . Ideally, a refinement operator is locally finite, complete, and prop er. In this article we show that if an element in a quasi-ordered set (S, greater than or equal to) has an infinite or incomplete cover set, then an ideal refinement operator for (S, greater than or equal to) d oes not exist. We translate the nonexistence conditions to a specific kind of infinite ascending and descending chains and show that these c hains exist in unrestricted sets of clauses that are ordered by theta- subsumption. Next we discuss how the restriction to a finite ordered s ubset can enable the construction of ideal refinement operators. Final ly, we define an ideal refinement operator for restricted theta-subsum ption ordered sets of clauses. (C) Elsevier Science Inc., 1998.