Nonterminal separation in graph grammars
type: Item
instance of: scholarly article
title: Nonterminal separation in graph grammars
zbMATH Open document ID: 0727.68059
DOI: 10.1016/0304-3975(91)90174-Z
author: Joost Engelfriet
author: George Leih
author: Grzegorz Rozenberg
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: The eNLCE model of graph grammars was introduced as a variation of the successful NLC model. In a NLC grammar the left hand side of a production is a single labeled node, the right hand side is a node labeled graph and the embedding mechanism depends solely on the labels of the nodes involved. In the case of eNCE grammars the embedding mechanism makes use of the identity (rather than the label) of the nodes in the right-hand side of the productions, the generated graphs have also edge labels, the embedding mechanism also uses the labels of the edges incident with the replaced node. In a previous paper the authors have shown that eNCE grammars are more powerful than NLC grammars. It also shown that boundary eNCE grammars (such that there are no edges between nonterminal nodes in any sentential form or, in other words, such that the distance between nonterminals is at least two) are confluent (namely, if two nodes in a graph can be replaced they can be replaced in any order). The present paper investigates the general notion of distance between nonterminal nodes in eNCE grammars. An eNCE grammar is called k- separated, for \(k\geq 1\), if the distance between any two nonterminal nodes in its sentential forms is \(\geq k\). Having previously shown that 1- separated grammars are more powerful than 2-separated grammars, the authors prove that 2-separated grammars are more powerful than 3- separated grammars and conjecture that, for \(k\geq 3\), k-separated grammars are more powerful than \((k+1)\)-separated grammars. Another considered restriction on graph grammars is an apex restriction. An eNCE grammar is an apex eNCE grammar if the embedding mechanism can only establish edges between terminal nodes. For apex grammars to be k- separated has no influence on the generating power, namely it is shown that each apex language can be generated by a k-separated apex grammar.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4201634
zbMATH Keywords: graph grammars
zbMATH Keywords: NLC grammar
zbMATH Keywords: eNCE grammars
reviewed by: Andrea Maggiolo-Schettini
MaRDI profile type: Publication
cites work: Position-restricted grammar forms and grammars
cites work: Q3785989
cites work: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
cites work: Q1839237
cites work: Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
cites work: Linear graph grammars: Power and complexity
cites work: Complexity of boundary graph languages
cites work: Apex graph grammars and attribute grammars
cites work: Q3785994
cites work: Boundary graph grammars with dynamic edge relabeling
cites work: A comparison of boundary graph grammars and context-free hypergraph grammars
cites work: Syntactic Analysis and Operator Precedence
cites work: On the structure of node-label-controlled graph languages
cites work: Restrictions, extensions, and variations of NLC grammars
cites work: Graph grammars with neighbourhood-controlled embedding
cites work: Q3714485
cites work: Q3785990
cites work: On generators and generative capacity of EOL forms
cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
cites work: Graph theoretic closure properties of the family of boundary NLC graph languages
cites work: Combinatorial properties of boundary NLC graph languages
full work available at URL: 0304-3975(91)90174-z
OpenAlex ID: W2004135004
description: scientific article; zbMATH DE number 4201634