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 approches 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: (or ) where 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 glueing graph. A rewriting step or application of a rule r to a host graph G is defined by two pushout diagrams both orginating in the same morphism (this is where the name double-pushout comes from). The graph morphism m models an occurence of L in G and is called a match. Practical understanding of this is that L is 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: . Thus a rewriting step is defined as 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.

See also

• Category theory