domingo, 26 de febrero de 2012

derivations II

derivations and direct derivations. Part II (non-determinism)

In a previous post I introduced derivations in MGG. Today I want to give you my personal interpretation of what a direct derivation is. Also, there is one problem that needs to be addressed in order to move forward: Potential dangling edges. MGG takes care of them through so-called epsilon-productions (e-productions). I will address them in the next post.

One question that I find pretty natural is why applying a production to some host graph is so complicated. There are several steps involved. For example, in the categorical approaches (SPO/DPO) we use one pushout construction (or even "worse", two pushout constructions) to define what a direct derivation is. My personal view is that the pushout construction is a device to transform a production into a function. This is not the standard point of view, in which the grammar is/specifies the function.

However, I think that the underlying idea of a production should be that of a function, which is straightforward. Direct derivations as introduced so far in the literature are not (they are not straightforward and they are not functions). Recall that a production applies a single graph into another graph. I think it should rather be a receipt to transform graphs into graphs (production and grammar rule are synonymous; the term rule and receipt are not that far in my opinion).

Nonetheless, my main objection to the pushout construction is its inherent non-determinism. In a more functional style I would say that it defines a multivalued function (one that assigns several different outputs to a single input). This is a far-reaching subject. For example, if SPO was used as a model of computation, e.g. to study the PvsNP problem, we would not get too far. Unfortunately, I think we would not even start because the definition of the complexity class P could not be done. By the way, I am not aware of any attempt to use/study DPO or SPO as a model of computation, even though most of the research in this field is carried out by computer scientists. No doubt, this is an extremely interesting topic.

How can we avoid this non-determinism in the different approaches to graph transformation? In my personal opinion, I think we cannot or at least I do not see how (I mean an easy way). How can we avoid this non-determinism in MGG? Recall that in MGG we can split the dynamics of the production from its statics, so to speak. One possibility are the so-called swaps, which are introduced in this preliminar paper (the full version has been published in the Electronic Journal of Combinatorics).

The obvious drawback of swaps is precisely that we lose non-determinism. Actually, it can be recovered but we shall leave this to a post dedicated solely to swaps.

Today's quote (Johnson Samuel) I do not agree. In fact, I think this is probably the main problem in mathematics and this blog's very initial reason for being: Sir, I have found you an argument. I am not obliged to find you an understanding. It is also possible to illustrate one's opinion using counterexamples...

viernes, 17 de febrero de 2012

derivations I

derivations and direct derivations. Part I

Recall that a production (or grammar rule) specifies how one graph is transformed into another. Following the intuition behind automatas or Turing Machines, we want to establish a procedure to pass from one state of a predetermined system to another, hence simulating its behaviour. In graph grammars, the state of a system is fixed by an associated graph. The idea is very simple: Apply the production to the initial state of the system and derive a new (system) state. This is precisely a direct derivation: The application of some production to some graph. A derivation is just a sequence of direct derivations.

The question that rises naturally is how this application is performed. The answer depends on the chosen approach to graph transformation. For example, in DPO the construction consists in essence of two double pushouts diagrams while in SPO it is a single pushout construction. Whatever the chosen approach is, the following steps are always fulfilled:
   1. Select grammar rule.
   2. Find occurrence of the grammar rule's left hand side (LHS) in the host (initial) graph.
   3. Check application conditions.
   4. Remove elements that appear in the left but not in the right hand side (RHS).
   5. Glue the elements of the right hand side to the graph of previous step.

MGG also follows more or less these same steps. Let's briefly comment on them. Regarding the selection on rules, there is no standard way (notice that a sequence precisely specifies this order of application). This is a clear source of non-determinism and we shall come back to it when we comment on MGG as a model of computation, sometime in the future.

The occurrence of the LHS is carried out through matching. This is addressed in Chap. 5 in the MGG book. There are two equivalent proposals, one using category theory (similar to the categorical approaches) and the other (novel) defining an operator that enlarges the LHS of the production. The basic remark is that a match is nothing but a production that transforms the LHS into the host graph. Then, we can define an operator that basically performs a continuation of the production (enlarges the production) such that it is perfectly suited for the graph it is going to be applied to.

I will write some posts on application conditions and graph constraints, so I will not touch step 3 here. Steps 4 and 5 are easily addressed through Boolean operations, as explained in this post. As nodes can be deleted, step 4 is potentially unsafe because some edges may dangle. Next post will be on dangling edges and how they are addressed in MGG.

As stated in previous posts, the way MGG handles productions and direct derivations has several advantages, and no real inconvenient as far as I can see. Please, comment if you have a different opinion.

Today I quote Oliver Heaviside. Should I refuse a good dinner simply because I do not understand the process of digestion?