Please Enter a Search Term
Departmental Seminar Apr 3rd: Robert Hamilton
Paul Price

Robert Hamilton
Honours Presentation
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.

Mar 26th, 2012

Bookmark and Share