The structure-mapping engine: Algorithm and examples

Brian Falkenhainer*, Kenneth D. Forbus, Dedre Gentner

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

980 Scopus citations

Abstract

This paper describes the structure-mapping engine (SME), a program for studying analogical processing. SME has been built to explore Gentner's structure-mapping theory of analogy, and provides a "tool kit" for constructing matching algorithms consistent with this theory. Its flexibility enhances cognitive simulation studies by simplifying experimentation. Furthermore, SME is very efficient, making it a useful component in machine learning systems as well. We review the structure-mapping theory and describe the design of the engine. We analyze the complexity of the algorithm, and demonstrate that most of the steps are polynomial, typically bounded by O(N2). Next we demonstrate some examples of its operation taken from our cognitive simulation studies and work in machine learning. Finally, we compare SME to other analogy programs and discuss several areas for future work.

Original languageEnglish (US)
Pages (from-to)1-63
Number of pages63
JournalArtificial Intelligence
Volume41
Issue number1
DOIs
StatePublished - Nov 1989

Funding

This research is supported by the Office of Naval Research, contract no. N00014-85-K-0559. Additional support has been provided by IBM, both in the form of a Graduate Fellowship for Falkenhainer and a Faculty Development award for Forbus. The equipment used in this research was provided by an equipment grant from the Information Sciences Division of the Office of Naval Research, and by a gift from Texas Instruments.

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'The structure-mapping engine: Algorithm and examples'. Together they form a unique fingerprint.

Cite this