related approaches III

Main graph transformation approaches part 3 and last.


Here I close these three posts dedicated to other approaches to graph transformations or graph dynamics. I will almost limit today to an enumeration of them.


The so-called set theoretic or algorithmic approaches are node replacement and hyperedge replacement. The basic idea of node replacement is to substitute one node in the host graph with another graph. As always, this is specified by a production but this time the left hand side of the production (the initial set of the "function") is normally made up of a single node. Usually, this node also appears in the codomain (the right hand side). There are many variants grouped under the general term "node replacement". NLC, NCE, edNCE, etcetera.

The hyperedge replacement approach is quite similar to the node replacement approach, but acting on edges instead of nodes, i.e. edges are substituted by graphs. Conceptually, there are few similarities between these two approaches and MGG. Most of the comments that I make here for DPO/SPO apply - in my opinion - to the algorithmic approaches and also to the MSOL approach.

Monadic Second Order Logics (MSOL) have been used by Courcelle et al. to model graph dynamics and the transformations are defined in terms of MSOL formulas (known as definable transductions). Again, from the conceptual point of view, there are very few similarities between the MSOL approach and MGGs, hence being difficult to make a comparison.

I finish this review by commenting on the relational approach. This one is more algebraic in its origins as it uses relations to define the dynamics (recall that a relation between the sets S and T is a subset of the Cartesian product S*T). However, it promptly tends to Dedekind categories, becoming closer and closer to the categorical approaches. In fact, Dedekind categories provide a variation of the DPO approach in which there are graph variables and replication is possible. We will touch on variables when we introduce graph constraints. Replication has not been introduced in MGGs so far, though my personal view is that it is not a basic operation, i.e. if replication is needed then an algorithm should be defined to carry it out (something I have not tried, to be honest, but that does not seem to be too difficult).

There is a small overview of all these approaches in Chap. 3 of the MGG book and a much more comprehensive one in the three volumes series "Handbook of graph grammars and computing by graph transformation".

Let's end witha cite from Raymond Louis Wilder: There is nothing mysterious, as some have tried to maintain, about the applicability of mathematics. What we get by abstraction from something can be returned.