Linear graph grammars: Power and complexity (Q1825679)

The authors consider linear graph grammars with neighbourhood controlled embedding and with dynamic edge relabelling, linear eNCE grammars. With respect to generative power they are shown to be equivalent to eNCE grammars that can generate only graphs with a bounded number of non- terminal nodes and to graph grammars in whose language every graph has at least one derivation involving graphs with a bounded number of non- terminal nodes. This is in direct contrast to the corresponding situation for context-free string grammars. The membership problem for linear eNCE languages with only connected graph of bounded degree is in NSPACE(log n) and hence in P, where n is the number of symbols needed to encode the graph (the paper does not clarify which encodings are permitted; however, the algorithm given seems to assume a ``simple'' encoding as usual in graph algorithms). This result has an interesting application in proving complexity bounds for certain properties of graphs.