Graph expressions and graph rewritings
From MaRDI portal
Publication:3782818
DOI10.1007/BF01692060zbMath0641.68115MaRDI QIDQ3782818
Michel Bauderon, Bruno Courcelle
Publication date: 1987
Published in: Mathematical Systems Theory (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
Recognizable sets of graphs: equivalent definitions and closure properties, Graph decompositions and tree automata in reasoning with uncertainty, Automata-based Representations for Infinite Graphs, Unnamed Item, Algebraic structures of directed acyclic graphs: application to concurrent calculus, Separation results for separated apex NLC and NCE graph languages, Node rewriting in graphs and hypergraphs: A categorical framework, Basic notions of universal algebra for language theory and graph grammars, Confluence for graph transformations, Monadic second-order evaluations on tree-decomposable graphs, Hyperedge replacement jungle rewriting for term-rewriting systems and logic programming, An axiomatization of graphs, Recursive queries and context-free graph grammars, Modular tree transducers, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, Undecidability of the bandwidth problem on linear graph languages, A comparison of boundary graph grammars and context-free hypergraph grammars, An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Power properties of NLC graph grammars with a polynomial membership problem, The string generating power of context-free hypergraph grammars, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, Hypermap rewriting: A combinatorial approach, Algorithms for recognition of regular properties and decomposition of recursive graph families, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Conditional rewriting logic as a unified model of concurrency, The monadic second-order logic of graphs. VII: Graphs as relational structures, Infinite hypergraphs. II: Systems of recursive equations, Context-free hypergraph grammars have the same term-generating power as attribute grammars, Trading independent for synchronized parallelism in finite copying parallel rewriting systems, The equivalence of bottom-up and top-down tree-to-graph transducers, A partial k-arboretum of graphs with bounded treewidth, Nondeterministic operations on finite relational structures, 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, 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, The obstructions of a minor-closed set of graphs defined by a context-free grammar, Logical description of context-free graph languages, \(L(A)=L(B)\)? decidability results from complete formal systems, A comparison of compatible, finite, and inductive graph properties, Infinite hypergraphs. I: Basic properties, The monadic second-order logic of graphs. VIII: Orientations, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Independent parallelism in finite copying parallel rewriting systems, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, The complexity of graph languages generated by hyperedge replacement, Handle-rewriting hypergraph grammars, Recognizability of graph and pattern languages, A general framework for types in graph rewriting, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Graph decompositions for cartesian products, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph grammars and automata (survey)
- Algebraic characterization of reducible flowcharts
- On graph rewritings
- Fundamental properties of infinite trees
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Infinite hypergraphs. II: Systems of recursive equations
- IO and OI. I
- Pushout-Properties: An analysis of gluing constructions for graphs
- Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Transformations of structures: An algebraic approach
- Initial Algebra Semantics and Continuous Algebras
- Algebraic automata and context-free sets
- Automata in general algebras
- Two Families of Languages Related to ALGOL
