Boundary graph grammars with dynamic edge relabeling

DOI10.1016/0022-0000(90)90002-3zbMath0694.68049OpenAlexW2084959922WikidataQ54309721 ScholiaQ54309721MaRDI QIDQ909478

George Leih, Joost Engelfriet, Ermo Welzl

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90002-3

zbMATH Keywords

graph grammarscontext-freeness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (28)

Node replacements in embedding normal form. ⋮ Handle-rewriting hypergraph grammars ⋮ 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 ⋮ Complexity of boundary graph languages ⋮ Logical description of context-free graph languages ⋮ A hierarchy of eNCE families of graph languages ⋮ Exponential time analysis of confluent and boundary eNCE graph languages ⋮ On the structure of linear apex NLC graph grammars ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ Unnamed Item ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Quasi-rocking real-time pushdown automata ⋮ The bounded degree problem for non-obstructing eNCE graph grammars ⋮ 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 ⋮ Linear graph grammars: Power and complexity ⋮ Generating irregular partitionable data structures ⋮ 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
• Unnamed Item
• Restrictions on NLC graph 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
• Characteristics of graph languages generated by edge replacement
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Nonterminal bounded NLC graph grammars
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• A characterization of context-free string languages by directed node- label controlled graph grammars
• Graph grammars with neighbourhood-controlled embedding
• Parallel concepts in graph theory
• 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
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• On sequential and parallel node-rewriting graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity

This page was built for publication: Boundary graph grammars with dynamic edge relabeling