Note on node-rewriting graph grammars (Q796997)

The purpose of the paper is to discuss the relationship of two lines of development within the theory of graph grammars: the ''Berlin approach'' based on the glueing of graphs and the NLC (node label controlled) approach. In Berlin grammars an application condition is used for subgraph replacement whereas this is not the case in NLC grammars. In order to make the comparison possible, Berlin grammars without the application condition, called node-glueing grammars, are considered; on the other side a subclass of NLC grammars, NUNLC (neighbourhood-uniform- node-label-controlled) grammars is taken and it is proved that for every grammar of one type it is possible to construct one of the other type such that derivations are the same.