First Order Graph Grammars
Curtis R. Cook · SIAM Journal on Computing · 1974
In this paper we consider first order context-free, linear, and regular graph grammars and obtain many results similar to those for the corresponding string grammars. We obtain normal forms for context-free and regular graph grammars, simplification lemmas, and algorithms for membership, emptiness, finiteness and infiniteness. We show the relation between regular graph languages and regular sets and show that the set of graphs resembling the nonregular set $\{ a^n b^n | n \geqq 1\} $ is not generated by a first order context-free graph grammar. We also give several graphical characterizations of each of the three types of graph grammars.