Graph Grammars An Introduction to the Double Pushout Approach

Abstract: "Graph Grammars provide an intuitive description for the manipulation of complex structures based on graphs, for instance, data base systems, operating systems, and complex applicative software in general. The algebraic theory of graph grammars is a tentative to describe graph grammars and the gluing construction for graphs as the basic concepts for the construction of derivations. This report consists of four sections. In the first one we present a series of definitions and elementary results concerning graphs, graph morphisms and congruences on graphs, aiming at both establishing terminology for further sections, as well as making it as self-contained as possible. The second section introduces carefully and with extreme detail the formal description of a graph derivation and its abstract (categorical) properties. The third is based heavily upon the second in order to introduce the notion of graph derivation within the double-pushout approach (short DPA), while the last one presents some nice theoretical results concerning Church-Rosser properties and parallelism of graph derivations."