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.