Restrictions, extensions, and variations of NLC grammars

DOI10.1016/0020-0255(80)90039-0zbMath0452.68074OpenAlexW2002048494MaRDI QIDQ1148688

Grzegorz Rozenberg, Dirk Janssens

Publication date: 1980

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(80)90039-0

zbMATH Keywords

string languagesnode-label-controlled graph grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (36)

Node replacements in embedding normal form. ⋮ A pumping lemma and the structure of derivations in the boundary NLC graph languages ⋮ The complexity of connectivity problems on context-free graph languages ⋮ Graph theoretic closure properties of the family of boundary NLC graph languages ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ Eigenvalue location in graphs of small clique-width ⋮ The generating power of boundary NLC graph grammars and cycle graphs ⋮ Combinatorial properties of boundary NLC graph languages ⋮ String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing ⋮ Handle NLC grammars and r. e. languages ⋮ The bounded degree problem for eNCE graph grammars ⋮ A hierarchy of eNCE families of graph languages ⋮ Exponential time analysis of confluent and boundary eNCE graph languages ⋮ A characterization of context-free string languages by directed node- label controlled graph grammars ⋮ Decision problems for node label controlled graph grammars ⋮ Boundary graph grammars with dynamic edge relabeling ⋮ Results of NLC grammars with one-letter terminal alphabets ⋮ Edge-label controlled graph grammars ⋮ Graph grammars with neighbourhood-controlled embedding ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Graph grammars with path-controlled embedding ⋮ Node-label controlled graph grammars with context conditions ⋮ 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 ⋮ The bounded degree problem for NLC grammars is decidable ⋮ Representing graph families with edge grammars ⋮ Generating irregular partitionable data structures ⋮ Note on node-rewriting graph grammars ⋮ Restrictions on NLC graph 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

Cites Work

• On the structure of node-label-controlled graph languages

This page was built for publication: Restrictions, extensions, and variations of NLC grammars