An axiomatic definition of context-free rewriting and its application to NLC graph grammars
From MaRDI portal
The paper deals with graph grammars. An abstract notion of context-free grammar over an arbitrary class of combinatorial objects is introduced. The node-label controlled (NLC) graph grammars, which have been defined and investigated by Janssens, Rozenberg and Welzl, are studied from this point of view. A monadic second-order theory of context-free NLC sets of graphs appropriate for expressing properties of graphs is introduced. It is shown that this theory is decidable. Some decidability results of graph grammars obtained by other authors are simple consequences of this result.
Recommendations
- scientific article; zbMATH DE number 4051026
- scientific article; zbMATH DE number 177419
- scientific article; zbMATH DE number 4106286
- scientific article; zbMATH DE number 17539
- Context-free hypergraph grammars with node rewriting
- Note on node-rewriting graph grammars
- scientific article; zbMATH DE number 3909759
- scientific article; zbMATH DE number 1062935
- scientific article; zbMATH DE number 1762783
- scientific article; zbMATH DE number 177438
Cites work
- Algebraic automata and context-free sets
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Decision problems for node label controlled graph grammars
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Graph expressions and graph rewritings
- Graph theoretic closure properties of the family of boundary NLC graph languages
- scientific article; zbMATH DE number 3846895 (Why is no real title available?)
- scientific article; zbMATH DE number 3943061 (Why is no real title available?)
- scientific article; zbMATH DE number 4035178 (Why is no real title available?)
- scientific article; zbMATH DE number 4049098 (Why is no real title available?)
- scientific article; zbMATH DE number 3615891 (Why is no real title available?)
- scientific article; zbMATH DE number 3633737 (Why is no real title available?)
- scientific article; zbMATH DE number 4124985 (Why is no real title available?)
- IO and OI. II
- Neighborhood-uniform NLC grammars
- Two Families of Languages Related to ALGOL
Cited in
(68)- Algorithms for graph problems on BNLC structured garphs
- The string generating power of context-free hypergraph grammars
- Hypermap rewriting: A combinatorial approach
- Order independent NCE grammars recognized in polynomial time
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- Context-free hypergraph grammars have the same term-generating power as attribute grammars
- NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
- The equivalence of bottom-up and top-down tree-to-graph transducers
- On hyperedge replacement and BNLC graph grammars
- Separating \(k\)-separated eNCE graph languages
- Hypergraph languages of bounded degree
- Monadic second-order definable graph transductions: a survey
- The complexity of connectivity problems on context-free graph languages
- 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
- 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
- Probabilistic hyperedge replacement grammars
- Monadic second-order definable text languages
- The monadic second-order logic of graphs. X: Linear orderings
- Logical description of context-free graph languages
- Generating irregular partitionable data structures
- Multiple context-free tree grammars: lexicalization and characterization
- Graph grammars according to the type of input and manipulated data: a survey
- Finite graph automata for linear and boundary graph languages
- The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
- HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
- Upper bounds to the clique width of graphs
- Grammars and clique-width bounds from split decompositions
- The complexity of graph languages generated by hyperedge replacement
- Node replacement graph grammars with dynamic node relabeling
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The monadic second-order logic of graphs, II: Infinite graphs of bounded width
- Pullback Grammars Are Context-Free
- Adaptive Star Grammars for Graph Models
- scientific article; zbMATH DE number 4106286 (Why is no real title available?)
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- scientific article; zbMATH DE number 177419 (Why is no real title available?)
- Recognizable sets of graphs: equivalent definitions and closure properties
- On the structure of linear apex NLC 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
- scientific article; zbMATH DE number 809155 (Why is no real title available?)
- Context-free hypergraph grammars with node rewriting
- Hyperedge replacement with rendezvous
- The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
- Decision problems for edge grammars
- A Greibach normal form for context-free graph grammars
- Separation results for separated apex NLC and NCE graph languages
- Node rewriting in graphs and hypergraphs: A categorical framework
- A uniform approach to graph rewriting: The pullback approach
- The monadic second-order logic of graphs : Definable sets of finite graphs
- Node rewriting in hypergraphs
- Basic notions of universal algebra for language theory and graph grammars
- Recursively indefinite databases
- Random graph generation in context-free graph languages
- Recursive queries and context-free graph grammars
- Nonterminal separation in graph grammars
- The monadic second-order logic of graphs. IV: Definability properties of equational graphs
- Boundary graph grammars with dynamic edge relabeling
- Edge-label controlled graph grammars
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Second-order abstract categorial grammars as hyperedge replacement grammars
- Adaptive star grammars and their languages
This page was built for publication: An axiomatic definition of context-free rewriting and its application to NLC graph grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102759)
