Nonterminal bounded NLC graph grammars (Q1114416)

The paper is dealing with graph grammars and graph languages, more precisely with NCE, NLC, NB-NCE, NB-NLC, LIN-NCE, and LIN-NLC graph languages. An NCE graph grammar (NCE stands for ``neighbourhood controlled embedding'') is a generative device \(G=(\Sigma\), \(\Delta\), P, S) that works in the same way as a context-free grammar, but the sentential forms of G are undirected graphs whose nodes are labelled with letters of the label alphabet \(\Sigma\). A production \(\pi =(X\), D, B) may be applied to a node \(v\) (labelled X) of a graph H as follows. The node \(v\) is removed from H, together with all incident edges and is replaced with the graph D. New edges are established between nodes of D and former neighbours of \(v\) according to the embedding relation B. An NLC graph grammar is an NCE grammar for which the embedding relation is defined as global over all productions in P. An NCE (NLC) grammar is termed nonterminal bounded with bound k, and is denoted as NB-NCE (respectively NB-NCL) grammar if each sentential form contains at most k nonterminals. For \(k=1\) we get LIN-NCE, and LIN-NLC grammars, respectively. The results of the paper concern the families generated by the above devices, and may be summarized by the following inclusion diagram: \[ \begin{matrix} &&&& NCE & = & NLC \\ &&&&& | \\ &&&& NB & - & NCE \\ &&& \diagup &&&& \diagdown \\ NB & - & NLC &&&&&& LIN & - & NCE \\ &&& \diagdown &&&& \diagup \\ &&&& LIN & - & NLC \end{matrix} \]