On hyperedge replacement and BNLC graph grammars
type: Item
instance of: scholarly article
title: On hyperedge replacement and BNLC graph grammars
zbMATH Open document ID: 0789.68087
DOI: 10.1016/0166-218X(93)90106-X
author: Walter Vogler
published in: Discrete Applied Mathematics
publication date: 1993-12-10T00:00:00Z
review text: The author compares two types of graph rewriting that may be taken for contextfree graph grammars: hyperedge replacement (replacing one hyperedge at each step) and boundary label controlled grammars (replacing one node at each step depending on the labels of its neighbours). To allow the comparison both approaches are slightly modified: Edge labels are introduced in BLNC grammars and node labels in HR grammars in such a way that they do not influence the replacement mechanism. Furthermore, the author restricts discussion to HR grammars which generate graphs only, although hypergraphs may occur as intermediate derivation steps. Each graph language generated by a modified HR grammar can also be generated by a modified BLNC grammar for which there exists a bound for the number of neighbours a nonterminally labelled node may have. The converse holds if we ignore the node labelling, and this restriction cannot be avoided. All the proofs are straightforward: a nonterminal hyperedge corresponds to a nonterminal node the neighbours of which correspond to the nodes the hyperedge visits. The paper is clearly written, and the reader may easily follow the proofs.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 464954
zbMATH Keywords: Node-label controlled grammars
zbMATH Keywords: graph rewriting
zbMATH Keywords: graph grammars
zbMATH Keywords: hyperedge replacement
zbMATH Keywords: hypergraphs
reviewed by: H. J. Schneider
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q3812222
cites work: Graph expressions and graph rewritings
cites work: Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
cites work: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Restrictions on 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: Q3785994
cites work: A comparison of boundary graph grammars and context-free hypergraph grammars
cites work: Hyperedge replacement: grammars and languages
cites work: Characteristics of graph languages generated by edge replacement
cites work: Q3774975
cites work: Q3789084
cites work: Q3795250
cites work: Graph minors. II. Algorithmic aspects of tree-width
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
description: scientific article; zbMATH DE number 464954