On sequential and parallel node-rewriting graph grammars. (English) Zbl 0531.68030

Summary: The aim of this paper is to discuss and compare two embedding mechanisms used in graph grammars: a connection relation mechanism (introduced by D. Janssens and G. Rosenberg [Inf. Sci. 20, 217-244 (1980; Zbl 0452.68074)]) and a stencil mechanism (introduced by K. Culik II and A. Lindenmayer [Proc. 8th Hawaii int. Conf. Syst. Sci., Honolulu 1975, 4-9 (1975; Zbl 0329.68062). In order to carry out such a comparison the use of a connection relation is modified to cover parallel rewriting (and the generation of node- and edge-labeled directed graphs) and the use of stencils is modified to cover sequential rewriting (and the generation of node-labeled undirected graphs).


68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI