### Abstract

Anti-unification guarantees the existence of a term which is an explicit representation of the most specific generalization of a collection of terms. This provides a formal basis for learning from examples. Here we address the dual problem of computing a generalization given a set of counter examples. Unlike learning from examples an explicit, finite representation for the generalization does not always exist. We show that the problem is decidable by providing an algorithm which, given an implicit representation will return a finite explicit representation or report that none exists. Applications of this result to the problem of negation as failure and to the representation of solutions to systems of equations and inequations are also mentioned.

Original language | English |
---|---|

Pages (from-to) | 301-317 |

Number of pages | 17 |

Journal | Journal of Automated Reasoning |

Volume | 3 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Sep 1987 |

Externally published | Yes |

### Keywords

- counter examples
- Herbrand universe
- learning disjunctive concepts
- machine learning

### Cite this

*Journal of Automated Reasoning*,

*3*(3), 301-317. https://doi.org/10.1007/BF00243794

}

*Journal of Automated Reasoning*, vol. 3, no. 3, pp. 301-317. https://doi.org/10.1007/BF00243794

**Explicit representation of terms defined by counter examples.** / Lassez, J. L.; Marriott, K.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Explicit representation of terms defined by counter examples

AU - Lassez, J. L.

AU - Marriott, K.

PY - 1987/9/1

Y1 - 1987/9/1

N2 - Anti-unification guarantees the existence of a term which is an explicit representation of the most specific generalization of a collection of terms. This provides a formal basis for learning from examples. Here we address the dual problem of computing a generalization given a set of counter examples. Unlike learning from examples an explicit, finite representation for the generalization does not always exist. We show that the problem is decidable by providing an algorithm which, given an implicit representation will return a finite explicit representation or report that none exists. Applications of this result to the problem of negation as failure and to the representation of solutions to systems of equations and inequations are also mentioned.

AB - Anti-unification guarantees the existence of a term which is an explicit representation of the most specific generalization of a collection of terms. This provides a formal basis for learning from examples. Here we address the dual problem of computing a generalization given a set of counter examples. Unlike learning from examples an explicit, finite representation for the generalization does not always exist. We show that the problem is decidable by providing an algorithm which, given an implicit representation will return a finite explicit representation or report that none exists. Applications of this result to the problem of negation as failure and to the representation of solutions to systems of equations and inequations are also mentioned.

KW - counter examples

KW - Herbrand universe

KW - learning disjunctive concepts

KW - machine learning

UR - http://www.scopus.com/inward/record.url?scp=0001323323&partnerID=8YFLogxK

U2 - 10.1007/BF00243794

DO - 10.1007/BF00243794

M3 - Article

AN - SCOPUS:0001323323

VL - 3

SP - 301

EP - 317

JO - Journal of Automated Reasoning

JF - Journal of Automated Reasoning

SN - 0168-7433

IS - 3

ER -