Graph rewriting

From Wikipedia, the free encyclopedia

In graph theory, graph rewriting is a system of rewriting for graphs. During the application of graph rewriting to a graph, subgraphs are replaced according to the rules of a rewrite system. Sometimes graph grammar is used as a synonym for graph rewriting system, especially in context of formal languages.

There are several approaches to graph rewriting, one of them is the algebraic approach, which is based upon category theory. Actually the algebraic approach is divided into at least three sub approaches: the double-pushout approach (DPO), the single-pushout approach (SPO) and (more recently) the pullback approach.

From the perspective of the DPO approach a graph rewriting rule is a pair of morphisms in the category of graphs with total graph morphisms as arrows: $r = (L \leftarrow K \rightarrow R)$ (or $L \supseteq K \subseteq R$ ) where $K \rightarrow L$ is injective. The graphs L and R are respectively called the left-hand side and the right-hand side of the rule. The graph K is called invariant or sometimes the gluing graph. A rewriting step or application of a rule r to a host graph G is defined by two pushout diagrams both originating in the same morphism $k\colon K\rightarrow G$ (this is where the name double-pushout comes from). Another graph morphism $m\colon L\rightarrow G$ models an occurrence of L in G and is called a match. Practical understanding of this is that $L$ is a subgraph that is matched from $G$ (see subgraph isomorphism problem), and after a match is found, L is replaced with R in host graph G where K serves as some kind of interface.

In contrast a graph rewriting rule of the SPO approach is a single morphism in the category labeled multigraphs with partial graph morphisms as arrows: $r\colon L\rightarrow R$ . Thus a rewriting step is defined by a single pushout diagram. Practical understanding of this is similar to the DPO approach. The difference is, that there is no interface between the host graph G and the graph G' being the result of the rewriting step.

There is also a more algebraic-like approach to graph rewriting, based mainly on Boolean algebra, called matrix graph grammars. This topic is expanded at mat2gra.info.

[edit] Implementations and applications

Tools that solve software engineering tasks (mainly MDA) with graph rewriting:
- GReAT
- VIATRA
- Fujaba uses Story driven modelling, a graph rewrite language based on PROGRES
Tools that are application domain neutral:
- GrGen.NET, a graph rewriter generator for C#
- AGG, the attributed graph grammar system (Java)