Graph grammars with neighbourhood-controlled embedding

A central feature that distinguishes graph grammars (we consider grammars generating sets of node-labelled undirected graphs only) from string grammars is that in the former one has to provide a mechanism by which a daughter graph (the right-hand side of a production) can be embedded in the rest of the mother graph, while in the latter this embedding is provided automatically by the structure that all strings possess (left-to-right orientation). In this paper we consider a possible classification of embedding mechanisms for (node-rewriting) graph grammars. This classification originates from the basic ideas of 9]. On the one hand it allows one to fit a number of existing notions of a graph grammar into a common framework and on the other hand it points out new “natural” possibilities for defining the embedding mechanism in a graph grammar. The relationship between the graph-language generating power of graph grammars using various embedding mechanisms is established.