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.

related approaches II

Main graph transformation approaches part 2

I continue today with SPO and DPO and my personal view of them. I want to start by acknowledging the deep and clever ideas and results that have been derived so far. If you are DPO/SPO fan, please, comment!

In my humble opinion, there are some advantages and disadvantages to the way DPO and SPO are defined. The good news are that both can deal with labelled multigraphs (which are of great interest to applied computer scientists) in a quite abstract way. MGG also deals with them (more on this in future posts). However...

From a theoretical point of view, in DPO/SPO you can not really study a production alone but one has to consider where that production is going to be applied. Roughly speaking, if I think of a production as a function that transforms a small set of elements, I have to specify all the domain and not just the part the function acts on. More technically, you have to study direct derivations and not productions. In my personal opinion, productions are the "natural" object of study and not direct derivations. Of course this is arguable. My main point here is that I would like to consider the functions that make up my graph transformation system (these are productions) and apply them to different systems (initial state), but I do not want to specify the system along with the functions (these are direct derivations), i.e. I would like to have uncoupled the functions and the actual set they are going to be applied to. Otherwise stated, I want to be able to specify my algorithm independently of the concrete instance of the problem it is going to be applied to.

In DPO (not in SPO) a direct derivation may specify the simultaneous addition and deletion of one element, say a node of a graph. This is a quite counter intuitive fact to me. I would say that one function may perform at most one action on one element. This has several consequences, mostly related to dangling conditions (edges incident to non-existent nodes). I will not enter this topic for now and leave it for a future posts on matching.

Nevertheless, my main slight objection is the difficulty in using other branches from mathematics. Some examples follow:

1. MGG generalizes previous approaches to graph constraints and application conditions through so-called diagrams (see Ch. 7 in the MGG Book). In essence, they plug monadic second order logics into MGG. I think that a similar construction is a hard task for DPO/SPO not to say for adhesive HLR categories.
2. When one studies sequences of productions and sequential independence (to what extent the order inside the sequence matters) groups of permutations arise naturally. They are easily handled in MGG (some posts on this topic to come) but I do not see an easy way (nor a difficult one) to do the same in DPO. We are thus limited for the moment, as far as I know, to study pairs of productions through the critical pairs lemma, which is a clear limitation as the results of Ch. 6 in the MGG book show.
3. Some concepts - which I find natural - are not so straightforward to define. What is called the nihil matrix in MGG (Sec. 4.4 in the MGG book; basically elements that "should not be") does not have a clear counterpart. It is one of the fundamental pieces to build bridges between MGG and complex analysis (some preliminar results can be found in this paper).
4. Complexity theory is probably the most prominent area of modern computer science. How does one study DPO/SPO as model of computations? What are their relationships with other models such as Turing Machines and Boolean Circuits? Are there interesting submodels of computation? To the best of my knowledge there is no attempt to study this, in my opinion due to its inherent difficulty. I will dedicate several posts to this particular topic for MGG in the future.
5. Other promising directions of research are for example the introduction of harmonic analysis. Notice that productions have a kind of linear structure, which can be studied with the Fourier transform over locally compact Abelian groups. This is my current research topic. Due to the abstractness of the pushout construction, this kind of stuff seems to lie too far from DPO/SPO.
   

There are other examples but I think previous points illustrate my view. Please, do not misunderstand my criticism because I do acknowledge the importance of DPO and SPO (visit this webpage for its current state and available tools). I just try to highlight the potential benefits to moving (or at least complement) from a categorical perspective to a more purely algebraic point of view, i.e. MGG. The next post will not be so long. I will try to brush over other approaches to graph dynamics.


Another quote from Alfred North Whitehead which I absolutely subscribe: Fundamental progress has to do with the reinterpretation of basic ideas.

---