Deriving graphs from graphs by applying a production

Abstract

Grammar-like systems for manipulating directed graphs (together with information associated with individual nodes and arcs) have many uses in computing but have not been studied as deeply, elegantly, and fruitfully as classical string grammars or even tree grammars. Satisfactory definitions of the most basic concepts have been elusive. When can the left side of a production be said to occur in a graph ? In replacing an occurrence of the left side of a production by the right side, how is the right side to be connected with the rest of the graph ? Ehrig, Pfender, and Schneider recently proposed general definitions adequate for a variety of applications and established some fundamental properties of graph grammars. This paper generalizes and sharpens their work so as to cover more applications. The exposition is mathematically rigorous but departs from that of Ehrig, Pfender, and Schneider's paper in ways that will perhaps render the material more accessible to readers who are not algebraists. © 1975 Springer-Verlag.