Within Inductive Logic Programming, refinement operators compute a set of specializations or generalizations of a clause. They are applied in model inference algorithms to search in a quasi-ordered set for clauses of a logical theory that consistently describes an unknown concept. Ideally, a refinement operator is locally finite, complete, and proper. 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) does not exist. We translate the nonexistence conditions to a specific kind of infinite ascending and descending chains and show that these chains exist in unrestricted sets of clauses that are ordered by theta-subsumption. Next we discuss how the restriction to a finite ordered subset can enable the construction of ideal refinement operators. Finally, we define an ideal refinement operator for restricted theta-subsumption ordered sets of clauses. (C) Elsevier Science Inc., 1998. [References: 15]
展开▼