the very basics II

The very basics of graph dynamics: completion and compatibility


A production in MGG specifies some Boolean matrix operations. The first thing to do is to "complete" the matrices so the Boolean operations make sense. This is not a trivial fact because not only the number of elements in the matrices may differ but also their ordering. Somehow it has to be decided which nodes are the same in different graphs, respecting types. Notice that this is one source of non-determinism unless all types are different.


This property is closely related to the matching problem: Given a host graph (initial state to which the grammar is going to be applied), select the places where the productions are going to be applied.

Notice there is still another source of non-determinism in MGGs: A means to select the following production to be applied. This sort of non-determinism is avoided by providing a sequence of productions, which is nothing but a set of productions to be applied in a given order.

Completion is necessary to perform the algebraic operations and we will always assume in MGGs that it has been performed somehow. More on this in Sec. 4.2 of the MGG book. The two sources of non-determinism commented above are relevant if we consider MGG as a model of computation, which I will do in future posts.

Another algebraic need is compatibility. We give the adjacency matrix to specify the edges of a graph, which implicitly contains the nodes of the graphs. As productions may act on nodes independently, a vector of nodes is also given and we have to be sure that the adjacency matrix and the vector of nodes are compatible, i.e. they have the same nodes (no edge is incident to a node that does not belong to the graph). A production is said to be compatible if it outputs a compatible graph starting out of a compatible graph. A similar definition of compatibility is given for sequences in the MGG book (intermediate states have to be compatible).

Compatibility is in essence well-formedness of graphs.

I finish today with a quote from Richard Feynman: "The worthwhile problems are the ones you can really solve or help solve, the ones you can really contribute something to. ... No problem is too small or too trivial if we can really do something about it."

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.