A comparison of boundary graph grammars and context-free hypergraph grammars
From MaRDI portal
Publication:918718
DOI10.1016/0890-5401(90)90038-JzbMath0706.68067MaRDI QIDQ918718
Joost Engelfriet, Grzegorz Rozenberg
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Related Items
Unnamed Item, Separation results for separated apex NLC and NCE graph languages, Node rewriting in graphs and hypergraphs: A categorical framework, Algorithmic uses of the Feferman-Vaught theorem, Nonterminal separation in graph grammars, The string generating power of context-free hypergraph grammars, The monadic second-order logic of graphs. VII: Graphs as relational structures, Context-free hypergraph grammars have the same term-generating power as attribute grammars, On hyperedge replacement and BNLC graph grammars, Separating \(k\)-separated eNCE graph languages, Hypergraph languages of bounded degree, Monadic second-order definable graph transductions: a survey, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, The translation power of top-down tree-to-graph transducers, Context-free graph languages of bounded degree are generated by apex graph grammars, The bounded degree problem for eNCE graph grammars, Logical description of context-free graph languages, A hierarchy of eNCE families of graph languages, Finite graph automata for linear and boundary graph languages, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, Node replacements in embedding normal form., HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, The complexity of graph languages generated by hyperedge replacement, Handle-rewriting hypergraph grammars, Complexity of boundary graph languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boundary graph grammars with dynamic edge relabeling
- Graph theoretic closure properties of the family of boundary NLC graph languages
- Combinatorial properties of boundary NLC graph languages
- Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Apex graph grammars and attribute grammars
- Tree transducers, L systems, and two-way machines
- On the structure of node-label-controlled graph languages
- Graph grammars with neighbourhood-controlled embedding
- Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
- Linear graph grammars: Power and complexity
- Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
- On sequential and parallel node-rewriting graph grammars
- Complexity of boundary graph languages
- A taxonomy of problems with fast parallel algorithms
- The NP-completeness column: an ongoing guide
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Complexity of Finding Embeddings in a k-Tree
- Graph expressions and graph rewritings
- Translations on a context free grammar
