On the structure of node-label-controlled graph languages
From MaRDI portal
Publication:1148687
DOI10.1016/0020-0255(80)90038-9zbMath0452.68073OpenAlexW2006513683MaRDI QIDQ1148687
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)90038-9
Related Items
A pumping lemma and the structure of derivations in the boundary NLC graph languages ⋮ The complexity of connectivity problems on context-free graph languages ⋮ Handle-rewriting hypergraph grammars ⋮ 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 ⋮ Characteristics of graph languages generated by edge replacement ⋮ The bounded degree problem for eNCE graph grammars ⋮ Nonterminal bounded NLC graph grammars ⋮ Parsing of edNLC-graph grammars for scene analysis ⋮ Complexity of boundary graph languages ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ Single pushout transformations of equationally defined graph structures with applications to actor systems ⋮ Parallel high-level replacement systems ⋮ A hierarchy of eNCE families of graph languages ⋮ A uniform approach to graph rewriting: The pullback approach ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ Restrictions, extensions, and variations of NLC grammars ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ Exponential time analysis of confluent and boundary eNCE graph languages ⋮ 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 ⋮ 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 ⋮ Node-label controlled graph grammars with context conditions ⋮ On the interleaving semantics of transformation units — A step into GRACE ⋮ 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 ⋮ Pullback rewriting and applications ⋮ Processes and Local Actions ⋮ 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 ⋮ Node rewriting in graphs and hypergraphs: A categorical framework ⋮ Representing graph families with edge grammars ⋮ Linear graph grammars: Power and complexity ⋮ 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