The Abstraction/Implementation Model of Problem Reformulation

A good problem representation incorporates important problem constraints while hiding superfluous detail. This paper presents methods for abstracting a problem representation by making implicit problem properties into explicit properties of the representation. The mathematics of the abstraction search space are given in terms of model theory and universal algebra. The Behavioral Abstraction method uses predefined representation maps to lift a problem representation to an abstract theory. The Behavioral Congruence method generates abstract theories and representation maps which incorporate problem constraints expressed as Behavioral Equivalences. Two meta-level methods for generating Behavioral Equivalence theorems are given. The STRATA automatic programming system described in this paper is currently being implemented.