Linear graph grammars: Power and complexity
type: Item
instance of: scholarly article
title: Linear graph grammars: Power and complexity
zbMATH Open document ID: 0684.68088
DOI: 10.1016/0890-5401(89)90030-8
author: Joost Engelfriet
author: George Leih
published in: Information and Computation
publication date: 1989-01-01T00:00:00Z
review text: The authors consider linear graph grammars with neighbourhood controlled embedding and with dynamic edge relabelling, linear eNCE grammars. With respect to generative power they are shown to be equivalent to eNCE grammars that can generate only graphs with a bounded number of non- terminal nodes and to graph grammars in whose language every graph has at least one derivation involving graphs with a bounded number of non- terminal nodes. This is in direct contrast to the corresponding situation for context-free string grammars. The membership problem for linear eNCE languages with only connected graph of bounded degree is in NSPACE(log n) and hence in P, where n is the number of symbols needed to encode the graph (the paper does not clarify which encodings are permitted; however, the algorithm given seems to assume a ``simple'' encoding as usual in graph algorithms). This result has an interesting application in proving complexity bounds for certain properties of graphs.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4121465
zbMATH Keywords: linear graph grammars
MaRDI profile type: Publication
full work available at URL: 0890-5401(89)90030-8
OpenAlex ID: W2037692988
cites work: On the membership problem for regular DNLC grammars
cites work: Q3859267
cites work: The bandwidth problem for graphs and matrices—a survey
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: Nonterminal bounded NLC graph grammars
cites work: Apex graph grammars and attribute grammars
cites work: Q3785994
cites work: Boundary graph grammars with dynamic edge relabeling
cites work: Finite-Turn Pushdown Automata
cites work: Derivation-bounded languages
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Q5572939
cites work: Q3862379
cites work: On the structure of node-label-controlled graph languages
cites work: Decision problems for node label controlled graph grammars
cites work: A characterization of context-free string languages by directed node- label controlled graph grammars
cites work: Graph grammars with neighbourhood-controlled embedding
cites work: Q3673132
cites work: Q3657456
cites work: On sequential and parallel node-rewriting graph grammars
cites work: Q3714485
cites work: Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
cites work: Topological Bandwidth
cites work: Q3666286
cites work: Linear and Context-Free Graph Grammars
cites work: Q5674993
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
cites work: Tree-size bounded alternation
cites work: Q5678435
Recommended article: Q3219131
Recommended article: Q3339312
Recommended article: Q4438792
Recommended article: Q3787507
Recommended article: A note on the equivalence and complexity of linear grammars
Recommended article: Q4284250
Recommended article: Graph automata for linear graph languages
Recommended article: The power of programmed grammars with graphs from various classes
Recommended article: Linear-Ordered Graph Grammars: Applications to Distributed Systems Design
Recommended article: A COMPLEX MEASURE FOR LINEAR GRAMMARS
description: scientific article; zbMATH DE number 4121465