Supervisor: Dr. Todd Wareham
Practical Optimal-Solution Algorithms for Schema-Based Analogy Mapping
Department of Computer Science
Wednesday, April 4, 11:00 a.m., Room EN-2022
Over the last 20 years, analogy derivation has come to be at the heart of cognitive science. Asformulated in Gentner's structure-mapping theory, an analogy is a mapping between two vertex- andedge-coloured directed acyclic graphs. Unfortunately, the problem of analogical mapping is unlikelyto be solvable efficiently, as it has been shown to be inherently computationally difficult, or NPhard. It has been conjectured, however, that the use of schemas--input graphs which are small in sizeand structurally close to the optimal analogy may be one method to make analogies easier to deriveefficiently. In this thesis, we find that the use of schemas alone is not enough to allow for practicalanalogy mapping. We examine versions of the problem using schemas that are also restricted tovarious classes of graphs and show that analogy mappings using schemas are polynomial-timecomputable for some simple classes of graphs. For more complicated graph classes, we examine aselection of parameters that may allow for effectively polynomial-time, i.e. fixed-parameter,algorithms.