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 (32)
Monadic second-order definable graph transductions: a survey ⋮ Node replacements in embedding normal form. ⋮ Handle-rewriting hypergraph grammars ⋮ 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 equivalence of boundary and confluent graph grammars on graph languages of bounded degree ⋮ The bounded degree problem for eNCE graph grammars ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Complexity of boundary graph languages ⋮ Logical description of context-free graph languages ⋮ A hierarchy of eNCE families of graph languages ⋮ A uniform approach to graph rewriting: The pullback approach ⋮ Unnamed Item ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ The string generating power of context-free hypergraph grammars ⋮ HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting ⋮ Node replacement in hypergraphs: Simulation of hyperedge replacement, and decidability of confluence ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ Finite graph automata for linear and boundary graph languages ⋮ Separation results for separated apex NLC and NCE graph languages ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ Node rewriting in graphs and hypergraphs: A categorical framework ⋮ A Greibach normal form for context-free graph grammars ⋮ Unnamed Item ⋮ The complexity of the \(K_{n,n}\)-problem for node replacement graph languages ⋮ On hyperedge replacement and BNLC graph grammars ⋮ Nonterminal separation in graph grammars ⋮ Separating \(k\)-separated eNCE graph languages ⋮ Hypergraph languages of bounded degree
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
This page was built for publication: A comparison of boundary graph grammars and context-free hypergraph grammars
