Linear graph grammars: Power and complexity

DOI10.1016/0890-5401(89)90030-8zbMath0684.68088OpenAlexW2037692988MaRDI QIDQ1825679

George Leih, Joost Engelfriet

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

zbMATH Keywords

linear graph grammars

Mathematics Subject Classification ID

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

• Unnamed Item
• 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
• 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

This page was built for publication: Linear graph grammars: Power and complexity