Explicit representation of terms defined by counter examples

J. L. Lassez, K. Marriott

Research output: Contribution to journalArticleResearchpeer-review

73 Citations (Scopus)

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 languageEnglish
Pages (from-to)301-317
Number of pages17
JournalJournal of Automated Reasoning
Volume3
Issue number3
DOIs
Publication statusPublished - 1 Sep 1987
Externally publishedYes

Keywords

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

Cite this

@article{f065d547b1e14adba25c0c014d78e483,
title = "Explicit representation of terms defined by counter examples",
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.",
keywords = "counter examples, Herbrand universe, learning disjunctive concepts, machine learning",
author = "Lassez, {J. L.} and K. Marriott",
year = "1987",
month = "9",
day = "1",
doi = "10.1007/BF00243794",
language = "English",
volume = "3",
pages = "301--317",
journal = "Journal of Automated Reasoning",
issn = "0168-7433",
publisher = "Springer-Verlag London Ltd.",
number = "3",

}

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

In: Journal of Automated Reasoning, Vol. 3, No. 3, 01.09.1987, p. 301-317.

Research output: Contribution to journalArticleResearchpeer-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

VL - 3

SP - 301

EP - 317

JO - Journal of Automated Reasoning

JF - Journal of Automated Reasoning

SN - 0168-7433

IS - 3

ER -