Nonterminal bounded NLC graph grammars
type: Item
instance of: scholarly article
title: Nonterminal bounded NLC graph grammars
zbMATH Open document ID: 0662.68074
DOI: 10.1016/0304-3975(88)90148-X
author: Joost Engelfriet
author: George Leih
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: 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} \]
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4083005
zbMATH Keywords: nonterminal bounded grammars
zbMATH Keywords: linear grammars
zbMATH Keywords: graph grammars
zbMATH Keywords: graph languages
MaRDI profile type: Publication
cites work: Linear graph grammars: Power and complexity
cites work: Q3785994
cites work: On the structure of node-label-controlled graph languages
cites work: Graph grammars with neighbourhood-controlled embedding
full work available at URL: 0304-3975(88)90148-x
OpenAlex ID: W2067295777
description: scientific article; zbMATH DE number 4083005