Transformations of structures: An algebraic approach

This paper introduces a new mathematical approach to transformations of structures, where the concept of structure is extremely general. Many structures and transformations that arise in biology as well as computer science are special cases of our concepts. A structure may be changed by finding an occurrence of a pattern and replacing it by another pattern as specified by a rule. To prove theorems about long sequences of applications of complicated rules, we need precise and tractable mathematical definitions of rules and how to apply them. This paper presents such definitions and three fundamental theorems, together with brief remarks on applications to control flow analysis, record handling, and evaluation of recursively defined functions. Unlike some previous efforts toward a rigorous theory of transformations of structures, this paper uses ideas and results from abstract algebra to minimize the need for elaborate constructions.A condensation of an earlier version of this paper was presented as [9] at the 7th Symposium on Mathematical Foundations of Computer Science, September 1978, Zakopane, Poland. Work by Ehrig was partially supported by IBM Germany and IBM World Trade Corp. Work by Rosen and Maggiolo-Schettini was partially supported by the Laboratorio di Cibernetica del C.N.R.