Boundary NLC and partition controlled graph grammars. (English) Zbl 0643.68109

Graph-grammars and their application to computer science, 3rd Int. Workshop, Warrenton/Va. 1986, Lect. Notes Comput. Sci. 291, 593-609 (1987).
[For the entire collection see Zbl 0636.00013.]
The paper starts with a discussion of an application of graph grammars as means for determining polynomial-time recognizability of graph properties. Then boundary NLC graph grammars are reviewed with emphasis on the application outlined in the first part. Finally, partition controlled graph grammars are introduced as an extension of boundary NLC graph grammars which still preserves many of the properties of boundary NLC graph grammars and, moreover, allows a simple characterization result.


68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory


Zbl 0636.00013