Completeness and Properness of Refinement Operators

Patrick van der Laag and Shan-Hwei Nienhuys-Cheng. Journal of Logic Programming, 34(3):201--226, March 1998.

Abstract

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 \em locally finite, \em complete and \em proper. In this article we show that if an element in a quasi-ordered set $\SG$ has an infinite or incomplete cover set then an ideal refinement operator for $\SG$ 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.

BibTeX entry.

Completeness and Properness of Refinement Operators

Abstract

Other publications