sábado, 28 de abril de 2012

initial graphs

initial graphs (minimal and negative initial digraphs)

One of the main advantages of MGG over other approaches to graph transformation is its ability to study properties of the grammar independently of the initial state. Thus, it is possible to define an algortihm (productions of a grammar) and analyse some of its properties without taking into account the concrete problem it is going to be applied to.

For a given sequence, one natural question is the minimal (smallest) graph that we have to be given in order to apply the sequence. Recall that MGG is not only able to study the elements that have to be present in order to apply a production, but also those that must not be in the initial graph. The minimal initial digraph (MID) is precisely this smallest graph. The negative initial digraph (NID) specifies those elements that should not appear in the host graph. They both can be explicitely calculated. Sections 4.4 and 5.3 in the MGG book are devoted to this topic. It is interesting that we can use this concepts to contribute to Petri nets (Sec. 8.2).

The main importance of the initial digraphs is that they substitute the host graph in those cases where some initial state is mandatory. For example, when dealing with universal quantifiers in application conditions. Hence, the analysis of the grammar productions can be performed without the need of a concrete host graph.

In previous posts I have commented on non-determinism in MGG, being one of its sources how nodes across productions are related (whether two nodes of the same type in different productions have to be the same node or not). If we have in mind a concrete sequence, as soon as the left hand sides of the productions are matched in the state graph the non-determinism disappears. But the interesting part of the analysis is the one that happens before the productions are matched into the host graph. Recall that this non-determinism is classified as vertical and horizontal. The initial digraphs deal with horizontal non-determinism, so they contribute also to the study of the vertical non-determinism.

Depending on the way completion is carried out, different initial digraphs will be derived, giving rise to the notions of initial digraph set. The horizontal non-determinism needs further research. For some time I tried to address this issue using representation theory, which I will comment on in a future post. There is a fast introduction to representation theory here.

Summarizing, initial digraphs are interesting at least for three reasons: They keep independence in MGG of the analysis with respect to the host graph, they also help in the study of horizontal non-determinism and they answer the question of what is the smallest graph able to fire a sequence.

Today I find myself a bit sarcastic. Normally I choose quotes that are related to the topic of the post in some way, but today I cannot stand including the following phrase from David Hilbert: Some people have got a mental horizon of radius zero and call it their point of view.

martes, 10 de abril de 2012


marking places in the host graph

Non-determinism of MGG is a recurrent topic in this blog. It is a property that MGG shares with the rest of approaches to graph rewriting. However, there are several situations in which determinism is needed, even if we want to have a non-deterministic grammar.

Determinism needs arise naturally in MGG in the following three sample situations: Dangling edges, application conditions and splitting rule actions. The first I briefly explained in a previous post: In order to delete any possible edge we append an epsilon-production. Of course we must assure that both productions are applied to the same nodes (otherwise, dangling edges would not be removed).

I will touch application conditions in some future post. Application conditions are just what their name indicate: Properties that must be fulfilled by the host graph in order to apply the production. It should suffice to say that in MGG it is possible to calculate an equivalent sequence to a given production + application conditions. This sequence extends the production and again it is necessary to guarantee that all relevant productions will be applied to the same nodes. If you are interested in application conditions, they are addressed in Chap. 7 of the MGG book.

At times it is of interest to split a production into subproductions, whose overall effect are equivalent. A good example is reachability (some posts on it in the future). If productions of a certain type are split into two productions (one with the addition of elements and one with deletion of elements), then the state equation can gather more information. Clearly, both productions should be applied in the same elements. For reachability, refer to Chap. 8 of the MGG book.

How is this achieved in MGG?. The idea is quite simple but has some subtleties that I do not address here (see Sec. 5.2 of the MGG book): Just mark all nodes the first production is applied to. To this end, introduce a node of a new type (a type not present in the host graph nor in the LHS or RHS of the productions). Link this node to all nodes where the first production is applied. Alter the second production so, first, its LHS must find this element and its relevant incident edges and, second, it deletes this marking node (not its incident edges). Why the second grammar rule should not delete the incident edges is related to sequential independence and is explained in detail in the MGG book.

Today's quote I have chosen from the great Friedrich Nietzsche: there are no facts, only interpretations. I, as a mathematician, completely agree.