Normal forms for context-free node-rewriting hypergraph grammars

摘要

Confluent node-rewriting hypergraph grammars represent the most comprehensive known method for defining sets of hypergraphs in a recursive way. For a large natural subclass of these grammars, we show that the maximal rank of hyperedges indispensable for generating some set of hypergraphs equals the maximal rank of the hyperedges occurring in the hypergraphs of that set. Moreover, if such a grammar generates a set of graphs, one can construct from that grammar a C-edNCE graph grammar generating the same set of graphs.