Diagrammatic Transformation Processes on Relational Maps

Contents

Psychological evidence indicates that human reasoners solve spatial relational inferences by constructing and inspecting mental models in visuo-spatial working memory. From a computational point of view, this reasoning strategy seems to combine relational representations comparable to those described in the AI literature on qualitative spatial reasoning with the type of local spatial transformations that are characteristic of diagrammatic reasoning. However, applying local transformations to arbitrary relational representations involves solving the computationally intractable subgraph isomorphism problem. This paper describes a class of representations, relational maps, for which the problem becomes tractable and, as a consequence, for which diagrammatic inference is implementable by efficient local transformations.