Context-free NCE graph grammars.

*(English)*Zbl 0756.68070
Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 148-161 (1989).

Summary: [For the entire collection see Zbl 0726.00019.]

The aim of this paper is to show some close relationships between context-free graph grammars and concepts from string language theory and tree language theory. There are many kinds of context-free graph grammars [see, e.g., H. Ehrig, M. Nagl, G. Rozenberg and A. Rosenfeld [Lect. Notes Comput. Sci. 291, Springer-Verlag (1987, Zbl 0636.00013)]. Some are node rewriting and others are edge rewriting. In both cases a production of the grammar is of the form \(X\to(D,B)\). Application of such a production to a labeled graph \(H\) consists of removing a node (or edge) labeled \(X\) from \(H\), replacing it by the graph \(D\), and connecting \(D\) to the remainder of \(H\) according to the embedding procedure \(B\). Since these grammars are context-free in the sense that one node (or edge) is replaced, their derivations can be modeled by derivation trees, as in the case of strings. However, the grammar may still be context-sensitive in the sense that the (edges of the) graph generated according to the derivation tree may depend on the order in which the productions are applied. A graph grammar that does not suffer from this context-sensitivity is said to be confluent (or to have the finite Church-Rosser property) (see B. Courcelle [Theor. Comp. Sci. 55, 141-182 (1987; Zbl 0644.68095)] for a uniform treatment). Thus, for a confluent graph grammar \(G\), each derivation tree of \(G\) yields a unique graph in the graph language generated by \(G\). Due to this close relationship to (derivation) trees, the generated graph languages can be described in terms of regular tree languages and regular string languages. We will show this for the particular case of the (node rewriting) edNCE graph grammars, studied by M. Kaul [Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken, Ph. D. Thesis, FB Math. u. Inf. d. Univ. Passau (1985; Zbl 0587.68076)], F. J. Brandenburg [Lect. Notes Comput. Sci. 291, 99-111 (1987; Zbl 0643.68107); Lect. Notes Comput. Sci. 294, 227-236 (1988)], J. Engelfriet, G. Leih and G. Rozenberg [Lect. Notes Comput. Sci. 291, 167-185 (1987; Zbl 0643.68112); Theor. Comput. Sci. 82, No. 1, 95-111 (1991; Zbl 0727.68059)], R. Schuster [Graphgrammatiken und Grapheinbettungen: Algorithmen und Komplexität, Ph. D. Thesis, Report MIP-8711, University of Passau (1987)], J. Engelfriet, G. Leih and E. Welzl [J. Comput. Syst. Sci. 40, No. 3, 307-345 (1990; Zbl 0694.68049)], J. Engelfriet and G. Leih [Inf. Comput. 81, 88-121 (1989; Zbl 0684.68088)], J. Engelfriet and G. Rozenberg [Inf. Comput. 84, No. 2, 163-206 (1990; Zbl 0706.68067)] (and called DNELC grammars be F. J. Brandenburg [loc. cit.]).

The aim of this paper is to show some close relationships between context-free graph grammars and concepts from string language theory and tree language theory. There are many kinds of context-free graph grammars [see, e.g., H. Ehrig, M. Nagl, G. Rozenberg and A. Rosenfeld [Lect. Notes Comput. Sci. 291, Springer-Verlag (1987, Zbl 0636.00013)]. Some are node rewriting and others are edge rewriting. In both cases a production of the grammar is of the form \(X\to(D,B)\). Application of such a production to a labeled graph \(H\) consists of removing a node (or edge) labeled \(X\) from \(H\), replacing it by the graph \(D\), and connecting \(D\) to the remainder of \(H\) according to the embedding procedure \(B\). Since these grammars are context-free in the sense that one node (or edge) is replaced, their derivations can be modeled by derivation trees, as in the case of strings. However, the grammar may still be context-sensitive in the sense that the (edges of the) graph generated according to the derivation tree may depend on the order in which the productions are applied. A graph grammar that does not suffer from this context-sensitivity is said to be confluent (or to have the finite Church-Rosser property) (see B. Courcelle [Theor. Comp. Sci. 55, 141-182 (1987; Zbl 0644.68095)] for a uniform treatment). Thus, for a confluent graph grammar \(G\), each derivation tree of \(G\) yields a unique graph in the graph language generated by \(G\). Due to this close relationship to (derivation) trees, the generated graph languages can be described in terms of regular tree languages and regular string languages. We will show this for the particular case of the (node rewriting) edNCE graph grammars, studied by M. Kaul [Syntaxanalyse von Graphen bei Präzedenz-Graph-Grammatiken, Ph. D. Thesis, FB Math. u. Inf. d. Univ. Passau (1985; Zbl 0587.68076)], F. J. Brandenburg [Lect. Notes Comput. Sci. 291, 99-111 (1987; Zbl 0643.68107); Lect. Notes Comput. Sci. 294, 227-236 (1988)], J. Engelfriet, G. Leih and G. Rozenberg [Lect. Notes Comput. Sci. 291, 167-185 (1987; Zbl 0643.68112); Theor. Comput. Sci. 82, No. 1, 95-111 (1991; Zbl 0727.68059)], R. Schuster [Graphgrammatiken und Grapheinbettungen: Algorithmen und Komplexität, Ph. D. Thesis, Report MIP-8711, University of Passau (1987)], J. Engelfriet, G. Leih and E. Welzl [J. Comput. Syst. Sci. 40, No. 3, 307-345 (1990; Zbl 0694.68049)], J. Engelfriet and G. Leih [Inf. Comput. 81, 88-121 (1989; Zbl 0684.68088)], J. Engelfriet and G. Rozenberg [Inf. Comput. 84, No. 2, 163-206 (1990; Zbl 0706.68067)] (and called DNELC grammars be F. J. Brandenburg [loc. cit.]).

##### MSC:

68Q42 | Grammars and rewriting systems |