On hyperedge replacement and BNLC graph grammars (Q1308742)

The author compares two types of graph rewriting that may be taken for contextfree graph grammars: hyperedge replacement (replacing one hyperedge at each step) and boundary label controlled grammars (replacing one node at each step depending on the labels of its neighbours). To allow the comparison both approaches are slightly modified: Edge labels are introduced in BLNC grammars and node labels in HR grammars in such a way that they do not influence the replacement mechanism. Furthermore, the author restricts discussion to HR grammars which generate graphs only, although hypergraphs may occur as intermediate derivation steps. Each graph language generated by a modified HR grammar can also be generated by a modified BLNC grammar for which there exists a bound for the number of neighbours a nonterminally labelled node may have. The converse holds if we ignore the node labelling, and this restriction cannot be avoided. All the proofs are straightforward: a nonterminal hyperedge corresponds to a nonterminal node the neighbours of which correspond to the nodes the hyperedge visits. The paper is clearly written, and the reader may easily follow the proofs.