Graph grammars with neighbourhood-controlled embedding

DOI10.1016/0304-3975(82)90088-3zbMath0486.68075OpenAlexW2013956597MaRDI QIDQ1165019

Grzegorz Rozenberg, Dirk Janssens

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90088-3

zbMATH Keywords

classification of embedding mechanismsgrammars generating sets of node-labelled undirected graphsgraph-language generating power of graph grammarsnode rewriting graph grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (28)

\(k\)-NLC graphs and polynomial algorithms ⋮ Handle NLC grammars and r. e. languages ⋮ Nonterminal bounded NLC graph grammars ⋮ Complexity of boundary graph languages ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ Non-size increasing graph rewriting for natural language processing ⋮ A hierarchy of eNCE families of graph languages ⋮ A uniform approach to graph rewriting: The pullback approach ⋮ Exponential time analysis of confluent and boundary eNCE graph languages ⋮ Boundary graph grammars with dynamic edge relabeling ⋮ Results of NLC grammars with one-letter terminal alphabets ⋮ Edge-label controlled graph grammars ⋮ 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 ⋮ Graph grammars with path-controlled embedding ⋮ Order independent NCE grammars recognized in polynomial time ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Graph transformation through graph surfing in reaction systems ⋮ Finite graph automata for linear and boundary graph languages ⋮ Separation results for separated apex NLC and NCE graph languages ⋮ Node rewriting in graphs and hypergraphs: A categorical framework ⋮ Linear graph grammars: Power and complexity ⋮ Generating irregular partitionable data structures ⋮ Restrictions on NLC graph grammars ⋮ Node replacement graph grammars with dynamic node relabeling ⋮ Nonterminal separation in graph grammars ⋮ Separating \(k\)-separated eNCE graph languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions, extensions, and variations of NLC grammars
• Web grammars and several graphs
• Context-free graph grammars
• Separable graphs, planar graphs and web grammars

This page was built for publication: Graph grammars with neighbourhood-controlled embedding