related approaches I

Main graph transformation approaches part 1

Today I start a small series of posts that touch on the different approaches "available in the market" to graph dynamics. More material can be found in chapter 3 of the MGG book, and the reader is referred there for the missing details. Let's start saying that there is a very active community made up mainly of computer scientists dedicated to this topic. The ideas behind them are deep and the results derived after over almost 40 years of research very interesting.

Nowadays, no doubt, the most important approach to graph transformation is the one known as algebraic approach. However, I will refer to it as categorical approach because it uses category theory. There is no algebra in it. In fact, it is not a single approach: At least there exist the single pushout (SPO) and the double pushout (DPO) approaches, and a generalization known as adhesive HLR categories (AHLRC). A good book on the topic is this one.

The main advantage of using category theory, in principle, is that once a result is established, it applies to any mathematical structure that belongs to that category. However, DPO and SPO should not be thought of as theories that study a concrete category, but rather as using a categorical construction to define the application of a production to a concrete host graph (this is known as a derivation). In particular, SPO uses a pushout construction and DPO uses two pushout constructions. (This is explained in detail in pp. 22 and 23 and 41-49 in the MGG book.) The one that does study categories to which results can be extended is AHLRC. As far as I know, AHLRC only deals with DPO and in general does not apply to SPO.

The next post is about what I see as advantages and "problems" of SPO and DPO. It is just my personal view


I quote Alfred North Whitehead to finish today's post: Everything of importance has been said before by somebody who did not discover it.

a bit of history

How it all started, its current state and my future plans


Some years ago, in order to finish my phD, I looked for the advice of professor Roberto Moriyón, head of the computer science department (Escuela Politécnica Superior) at U.A.M. He kindly explained to me what the research activity was and what he thought could be more interesting for me.

So following Roberto's advice I met Juan de Lara who proposed to study distributed simulation protocols using graph transformation systems. I immediately became interested in the topic and started to study the so-called algebraic approach to graph transformation. Actually it uses category theory. (I will comment on this and other approaches in a future post.)

Not much time passed before I started to miss a real algebraic approach to graph transformation and it seemed to me that it should not be too difficult to begin with one. So I sent to Juan a new thesis proposal (in fact, seven in a few weeks) which would become the seeds of Matrix Graph Grammars. In them I included an algebraic (Boolean) characterization of production (a production is just a function - or morphism or application - that transforms one graph into another graph), an initial characterization of sequential independence (to what extent the order of productions inside a sequence matters) and some comments on parallelism (in essence, if two productions can be applied in any order without altering the resulting graph).
We then started to develop such approach by studying completion, coherence, initial digraphs, composition, matching, sequentialization, parallelism, restrictions (graph constraints and application conditions) and reachability. I will dedicate some posts to all of them. In some hard-to-explain sense, I feel that they are a "closed" set of results. This is basically what the Matrix Graph Grammars book include.

My intention for the future is to write a second volume, to get to complexity theory. The first few results can be found here. I need to present MGG as a model of computation, which is not foreseen to be very difficult. I'll touch on this too, but probably not soon. Some topics that I would also love to include are termination and confluence (basically, existence and uniqueness) but it takes time... We'll see.


Erwin Schrödinger once wrote: No self is of itself alone.