Explicit representation of terms defined by counter examples (Q1100924)

A finite representation for an implicit generalization of a collection of terms is investigated. Such finite representation for the generalization does not always exist. It is shown that the problem is decidable. An algorithm exists which, given an implicit representation will return a finite explicit representation or report that none exists. Transforming an implicit representation into an equivalent disjunction of terms is of importance to machine learning as it allows disjunctive concepts to be learnt from examples with counter examples. The basic results on generalization and learning given in this paper also have applications in other areas. It is shown that the algorithm provided is relevant to the representation of solutions to systems of equations and inequations and to the negation as failure problem.