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)
Related Items
On systems of equations defining infinite graphs, The monadic second-order logic of graphs : Definable sets of finite graphs, 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, 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, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Probabilistic hyperedge replacement grammars, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Constraint relaxation may be perfect, An axiomatic definition of context-free rewriting and its application to NLC graph grammars, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Recognizable sets of graphs: equivalent definitions and closure properties, Graph decompositions and tree automata in reasoning with uncertainty, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, Uniform parsing for hyperedge replacement grammars, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, The obstructions of a minor-closed set of graphs defined by a context-free grammar, Logical description of context-free graph languages, Power properties of NLC graph grammars with a polynomial membership problem, Graph-grammar semantics of a higher-order programming language for distributed systems, Graphs and designing, Set-theoretic graph rewriting, On relating rewriting systems and graph grammars to event structures, Recognizable languages of arrows and cospans, An introduction to category-based equational logic, Reachability in Graph Transformation Systems and Slice Languages, Maximum flows in parametric graph templates, Monoidal Width, Rewriting logic as a semantic framework for concurrency: a progress report, Unification of drags and confluence of drag rewriting, The generative power of delegation networks, A uniform approach to graph rewriting: The pullback approach, Monoidal Width: Capturing Rank Width, Automata-based Representations for Infinite Graphs, Undecidability of the bandwidth problem on linear graph languages, From Tree-Based Generators to Delegation Networks, Algebraic structures of directed acyclic graphs: application to concurrent calculus, Graph transformation for incremental natural language analysis, A comparison of boundary graph grammars and context-free hypergraph grammars, Independent parallelism in finite copying parallel rewriting systems, HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting, 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, Basic notions of universal algebra for language theory and graph grammars, Confluence for graph transformations, Conditional rewriting logic as a unified model of concurrency, A category-theoretical approach to vertex replacement: The generation of infinite graphs, Graph unification and matching, The use of tree transducers to compute translations between graph algebras, Process specification and verification, The obstructions of a minor-closed set of graphs defined by hyperedge replacement can be constructed, Concatenation of graphs, HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting, A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths, The monadic second-order logic of graphs. VII: Graphs as relational structures, Multiple context-free tree grammars: lexicalization and characterization, Monadic second-order evaluations on tree-decomposable graphs, Hyperedge replacement jungle rewriting for term-rewriting systems and logic programming, Infinite hypergraphs. II: Systems of recursive equations, Context-free hypergraph grammars have the same term-generating power as attribute grammars, The monoidal structure of Turing machines, Second-order abstract categorial grammars as hyperedge replacement grammars, Recognizability of graph and pattern languages, An axiomatization of graphs, Separation results for separated apex NLC and NCE graph languages, The complexity of graph languages generated by hyperedge replacement, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, Node rewriting in graphs and hypergraphs: A categorical framework, A Greibach normal form for context-free graph grammars, Treewidth and logical definability of graph products, Unnamed Item, Unnamed Item, Unnamed Item, Weighted parsing for grammar-based language models over multioperator monoids, A comparison of compatible, finite, and inductive graph properties, Trading independent for synchronized parallelism in finite copying parallel rewriting systems, Infinite hypergraphs. I: Basic properties, Causality in Bounded Petri Nets is MSO Definable, Recursive queries and context-free graph grammars, 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, Selected Decision Problems for Square-Refinement Collage Grammars, The monadic second-order logic of graphs. VIII: Orientations, \(L(A)=L(B)\)? decidability results from complete formal systems, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, On hyperedge replacement and BNLC graph grammars, A general framework for types in graph rewriting, Graph decompositions for cartesian products, Separating \(k\)-separated eNCE graph languages, Modular tree transducers, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, Hypergraph languages of bounded degree
Uses Software
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
