scientific article; zbMATH DE number 4049100
[For the entire collection see Zbl 0636.00013.] Graph grammars are systems for the generation of directed, node and edge labeled graphs. They rewrite single nodes only and establish connections between the inserted graph and the neighbors of the replacement node on the basis of node labels and edge labels. If there is only a single edge label, then graph grammars are closely related to NLC graph grammars. A partially ordered graph is a graph together with a spanning tree. These components are distinguished by their edge labels. A partially ordered graph grammar is the union of a graph grammar and a tree grammar. These components fit together such that their rewriting processes yield partially ordered graphs with the tree grammar generating spanning trees. Here we concentrate on the computational complexity of some restricted types of graph grammars and their languages with emphasis on intractability. It turns out that node and edge labeled tree grammars generate PSPACE-complete sets of connected graphs of finite degree, and that one-sided linear edge-unlabeled tree grammars generate NP-complete sets of graphs. However, the complexity is polynomial if the graphs have finite degree and are generated by a one-sided linear partially ordered graph grammar. This situation closely parallels the case of NLC and regular BNLC grammars. NLC graph grammars can be seen as undirected, edge-unlabeled graph grammars, and, on the other hand, edge-unlabeled undirected one-sided linear partially ordered graph grammars and edge- unlabeled undirected one-sided linear partially ordered tree-graph grammars are special BNLC graph grammars.
- Power properties of NLC graph grammars with a polynomial membership problem
- The bounded degree problem for eNCE graph grammars
- Generating irregular partitionable data structures
- The complexity of graph languages generated by hyperedge replacement
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 3872712 (Why is no real title available?)
- scientific article; zbMATH DE number 4051027 (Why is no real title available?)
- The bounded degree problem for non-obstructing eNCE graph grammars
- The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
- Exponential time analysis of confluent and boundary eNCE graph languages
- Tree-Based Generation of Restricted Graph Languages
- Nonterminal separation in graph grammars
- Boundary graph grammars with dynamic edge relabeling
- A comparison of boundary graph grammars and context-free hypergraph grammars
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785989)