An axiomatic definition of context-free rewriting and its application to NLC graph grammars
From MaRDI portal
Publication:1102759
DOI10.1016/0304-3975(87)90102-2zbMath0644.68095OpenAlexW1992040352MaRDI QIDQ1102759
Publication date: 1987
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(87)90102-2
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Monadic second-order definable graph transductions: a survey, The complexity of connectivity problems on context-free graph languages, Handle-rewriting hypergraph grammars, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, \(k\)-NLC graphs and polynomial algorithms, The translation power of top-down tree-to-graph transducers, Hyperedge replacement with rendezvous, Context-free graph languages of bounded degree are generated by apex graph grammars, Synthesized and inherited functions. A new computational model for syntax-directed semantics, The equivalence of boundary and confluent graph grammars on graph languages of bounded degree, Probabilistic hyperedge replacement grammars, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Monadic second-order definable text languages, Recognizable sets of graphs: equivalent definitions and closure properties, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, The monadic second-order logic of graphs. X: Linear orderings, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, Grammars and clique-width bounds from split decompositions, Logical description of context-free graph languages, Decision problems for edge grammars, A uniform approach to graph rewriting: The pullback approach, The monadic second-order logic of graphs : Definable sets of finite graphs, 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, Pullback Grammars Are Context-Free, Adaptive Star Grammars for Graph Models, Algorithms for graph problems on BNLC structured garphs, The string generating power of context-free hypergraph grammars, Hypermap rewriting: A combinatorial approach, Upper bounds to the clique width of graphs, Order independent NCE grammars recognized in polynomial time, Basic notions of universal algebra for language theory and graph grammars, A category-theoretical approach to vertex replacement: The generation of infinite graphs, HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting, Node replacement in hypergraphs: Simulation of hyperedge replacement, and decidability of confluence, Drawing graphs with attribute graph grammars, The monadic second-order logic of graphs. VII: Graphs as relational structures, Multiple context-free tree grammars: lexicalization and characterization, Graph grammars according to the type of input and manipulated data: a survey, Context-free hypergraph grammars have the same term-generating power as attribute grammars, Recursively indefinite databases, NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\), Context-free hypergraph grammars with node rewriting, Second-order abstract categorial grammars as hyperedge replacement grammars, Finite graph automata for linear and boundary graph languages, Separation results for separated apex NLC and NCE graph languages, Adaptive star grammars and their languages, The complexity of graph languages generated by hyperedge replacement, Node rewriting in graphs and hypergraphs: A categorical framework, A Greibach normal form for context-free graph grammars, Unnamed Item, Recursive queries and context-free graph grammars, The equivalence of bottom-up and top-down tree-to-graph transducers, Generating irregular partitionable data structures, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, 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, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, Hypergraph languages of bounded degree
Uses Software
Cites Work
- Graph theoretic closure properties of the family of boundary NLC graph languages
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Decision problems for node label controlled graph grammars
- IO and OI. II
- Neighborhood-uniform NLC grammars
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Graph expressions and graph rewritings
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Algebraic automata and context-free sets
- Two Families of Languages Related to ALGOL
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
