the very basics I

The very basics of graph dynamics: productions

Today I comment on productions. Productions encode the most important notion to study: Dynamics. Starting out from one graph (L) we obtain another one (R) and this operation is named p (the production).

MGG considers simple digraphs (graphs with no "parallel edges"). We will see that this scheme in fact permits MGG to deal with multidigraphs (graphs with "parallel edges").

There are two actions that can be performed: adding or deleting one element (element = node or edge). The main reason to concentrate on simple digraphs is that their edges can be faithfully represented by a Boolean matrix (adjacency matrix). As we may also add and delete nodes, we need one further vector to know if one node belongs to the graph or not.

The actions (graph dynamics, productions) are encoded through the AND and OR operations from Boolean logics. Define two new matrices: e specify elements to be deleted and r elements to be added. Starting from two graphs (L and R) that "statically" define one transformation (L becomes R) we introduce two matrices that acting on L have as result R:

$p:L \rightarrow R \qquad R = p(L) = r \vee \left( \overline{e} \wedge L \right) = r \vee \overline{e} L$

(By default, the and operation is not explicitly written, as in the last equality.) So (e,r) encode the dynamics of the production. There are at least two non-equivalent ways to make p become a transformation between graphs: Swaps and derivations. A production could be understood as a means to represent an application from the set of graphs to the set of graphs (in general a multivalued application). In contrast, a direct derivation is the transformation of a concrete graph. This is why I said in this post that I find more natural to study productions than direct derivations.

This production characterization is novel to the very best of my knowledge. It is pretty easy and with loads of consequences (this topic is fully developed in Chap. 4 of the MGG book):

1. It splits the "dynamics" (e, r) from the "statics" (L, R), so to speak.
2. Dynamics can be studied independently of the graph it is going to be applied to (known as host graph, more on this when we get to derivations). This can not be done by any other approach to graph transformation as far as I know. In my opinion it is the first big advantage of MGGs.
3. Even more so, it is possible to study the actions (e, r) independently from the graphs that define them (L, R). Its algebraic generalization gives rise to what are known as swaps. It will take us a little to get to them.
4. Notice the "affine" or "linear" shape of the function (production), p(x) = ax + b.

A very nice Australian proverb to close today's post: The more you know, the less you need.