Toward a model of representation changes

摘要

This paper presents the first steps in the development of a computer model of the process of changing representations in problem solving. The task of discovering representations that yield efficient solution strategies for problems is viewed as heuristic search in the space of representations. Two dimensions of this representation space are information structure and information quantity. Changes of representation are characterized as isomorphisms and homomorphisms, corresponding to changes of information structure and information quantity, respectively. A language for expressing representations is given. Also, a language for describing representation transformations and an interpreter for applying the transformations to representations has been developed. In addition, transformations can be automatically inverted and composed to generate new transformations. Among the example problems used to illustrate and support this model are tic-tac-toe, integer arithmetic, the Tower of Hanoi problem, the arrow puzzle, the five puzzle, the mutilated checkerboard problem, and floor plan design. The system has also been used to generate some new NP-complete problems.