Linear graph grammars: Power and complexity
From MaRDI portal
Publication:1825679
DOI10.1016/0890-5401(89)90030-8zbMath0684.68088OpenAlexW2037692988MaRDI QIDQ1825679
Publication date: 1989
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(89)90030-8
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Related Items (27)
Node replacements in embedding normal form. ⋮ Handle-rewriting hypergraph grammars ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ The bounded degree problem for eNCE graph grammars ⋮ Nonterminal bounded NLC graph grammars ⋮ Complexity of boundary graph languages ⋮ Logical description of context-free graph languages ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ A hierarchy of eNCE families of graph languages ⋮ The complexity of regular DNLC graph languages ⋮ Boundary graph grammars with dynamic edge relabeling ⋮ On the structure of linear apex NLC graph grammars ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ The string generating power of context-free hypergraph grammars ⋮ Graph automata for linear graph languages ⋮ HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Finite graph automata for linear and boundary graph languages ⋮ Separation results for separated apex NLC and NCE graph languages ⋮ A Greibach normal form for context-free graph grammars ⋮ Double Greibach operator grammars ⋮ The complexity of the \(K_{n,n}\)-problem for node replacement graph languages ⋮ Node replacement graph grammars with dynamic node relabeling ⋮ Nonterminal separation in graph grammars ⋮ Separating \(k\)-separated eNCE graph languages ⋮ Hypergraph languages of bounded degree
Cites Work
- Boundary graph grammars with dynamic edge relabeling
- On the membership problem for regular DNLC grammars
- 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
- Apex graph grammars and attribute grammars
- Nonterminal bounded NLC graph grammars
- Tree-size bounded alternation
- On the structure of node-label-controlled graph languages
- A characterization of context-free string languages by directed node- label controlled graph grammars
- Decision problems for node label controlled graph grammars
- Graph grammars with neighbourhood-controlled embedding
- 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
- Derivation-bounded languages
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- On sequential and parallel node-rewriting graph grammars
- Topological Bandwidth
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
- The bandwidth problem for graphs and matrices—a survey
- Finite-Turn Pushdown Automata
- Linear and Context-Free Graph Grammars
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Linear graph grammars: Power and complexity
