Graph rewriting systems have come of age. In autumn 1994, the 25th anniversary of
the first publication in this area was celebrated at the 5th Workshop on Graph
Grammars and their Applications to Computer Science. In the interim, the subject has
evolved. The current situation can be described by a three-stage model. At the very
low level there is a common idea of graph rewriting as the basic mechanism, where a
graph is transformed by the application of a rewriting rule.
In the second stage, this mechanism is expressed in several ways. Usually, two so
called approaches are distinguished: the algorithmic (or set-theoretic) and the
algebraic approach. Both provide a formalisation of graph rewriting. They give a
precise semantics to the idea of graph transformation and, hence, allow for a formal
treatment. In that sense, they are similar to the semantics of programming languages.
The upper stage is partitioned into several branches. At one extreme, theoretical
studies on the generational power, on semantic constructs, or on restricted formalisms
are undertaken. At the other extreme, specifications of real-world systems, or imple
mentations of rewriting environments are developed. Because the individual problems
to solve are complicated enough, the branches are not very aware of each other.
The monograph builds bridges between various areas of interest: 1) it studies a class
of graph rewriting systems which is very suitable for an efficient execution; 2) it
presents a compilation approach to the implementation of an environment for graph
rewriting; 3) it develops an implementation of a functional programming language to
show that and how the presented ideas apply to real-world problems.