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.

(tentative) intentions

Roadmap for the next months


My plan for the short-mid term for the blog is to provide a conceptual approach to graph transformation, keeping aside technicalities and concentrating mainly on the ideas, as proposed by Goldreich et al.

My (tentative) roadmap is the following: a few posts revisiting the history and background of MGG and related topics. I will comment on other approaches to graph dynamics. Then we will check the main concepts of MGG, "informally" so to speak: completion, coherence, initial digraphs, composition, matching, sequentialization, parallelism, restrictions (graph constraints and application conditions) and reachability. I will try to propose directions for further research if it seems to me that I have something sensible to say.

This will possibly amuse myself for several months. Later, or maybe in the meanwhile, I will touch on topics such as labelling, multigraphs and some others. More advanced topics will be also addressed. As we progress, we will be hopefully entering the realms of complexity theory.

From time to time I will insert non-related topics if I'm aware of something interesting in the world of mathematics. The main topic here is discrete mathematics but in principle I do not close the door to any interesting stuff.


Donald Knuth: The most important thing in the programming language is the name. A language will not succeed without a good name. I have recently invented a very good name and now I am looking for a suitable language.

MGG blog starts running!

Finally, I have decided to start this blog on Matrix Graph Grammars in blogger. Some of the entries were previously published in a blog that I maintained in my own server... but I gave up... this is easier, cheaper, ..., oh, dude.

I will try to maintain this blog entries as regularly as possible, but unfortunately this does not mean once per day or even once per week. My intention is to comment on what I'm currently investigating, mainly focused on matrix graph grammars, but it is possible that I might include other (un)related topics.

I'd like to include a quote in every post. The following one from Aristotle is illuminating: one swallow does not make a summer, nor does one day; and so too one day, or a short time, does not make a man blessed and happy.