Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
From MaRDI portal
Publication:3747744
DOI10.1016/S0019-9958(86)80045-6zbMath0608.68060OpenAlexW2061817376WikidataQ54309887 ScholiaQ54309887MaRDI QIDQ3747744
Grzegorz Rozenberg, Ermo Welzl
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80045-6
Related Items
Monadic second-order definable graph transductions: a survey, Node replacements in embedding normal form., A pumping lemma and the structure of derivations in the boundary NLC graph languages, Automatic graphs and D0L-sequences of finite graphs, On the membership problem for regular DNLC grammars, Handle-rewriting hypergraph grammars, Graph theoretic closure properties of the family of boundary NLC graph languages, On the structure of recognizable languages of dependence graphs, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, The generating power of boundary NLC graph grammars and cycle graphs, Context-free graph languages of bounded degree are generated by apex graph grammars, Combinatorial properties of boundary NLC graph languages, String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing, The equivalence of boundary and confluent graph grammars on graph languages of bounded degree, An axiomatic definition of context-free rewriting and its application to NLC graph grammars, The bounded degree problem for eNCE graph grammars, On the regularity and learnability of ordered DAG languages, Complexity of boundary graph languages, Metatheorems for decision problems on hyperedge replacement graph languages, Logical description of context-free graph languages, Power properties of NLC graph grammars with a polynomial membership problem, Equational Reasoning with Context-Free Families of String Diagrams, A hierarchy of eNCE families of graph languages, Graph-theoretic properties compatible with graph derivations, Undecidability of the bandwidth problem on linear graph languages, The complexity of regular DNLC graph languages, Boundary graph grammars with dynamic edge relabeling, 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, Quasi-rocking real-time pushdown automata, Algorithms for graph problems on BNLC structured garphs, Order independent NCE grammars recognized in polynomial time, Graph automata for linear graph languages, HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting, The monadic second-order logic of graphs. VII: Graphs as relational structures, Finite graph automata for linear and boundary graph languages, Separation results for separated apex NLC and NCE graph languages, The complexity of graph languages generated by hyperedge replacement, Unnamed Item, On structured graph grammars. I, Linear graph grammars: Power and complexity, Double Greibach operator grammars, On hyperedge replacement and BNLC graph grammars, Node replacement graph grammars with dynamic node relabeling, Nonterminal separation in graph grammars, Separating \(k\)-separated eNCE graph languages, Hypergraph languages of bounded degree
