miércoles, 11 de enero de 2012

the very basics III

The very basics of graph dynamics: the nihilation matrix.

Today I touch on the nihilation or nihil matrix. Recall that a production transforms one graph (L) into another (R). When a production is applied to some host graph G (which represents the state of the system under study), L is found in G and substituted by R to derive graph H (which is the new state of the system).

Notice that the left hand side of the productions (L) specifies what elements must be present in any host graph in order to apply the production. The nihilation matrix specifies what edges must not be present in order to apply the production. It is represented by K. There are two sets of edges that should not appear: Those incident to nodes that are deleted by the production and those that are going to be added by the production.

It is important to notice that the nihilation matrix only makes explicit some implicit information. Then, what is it good for? Actually it is extremely useful. First of all, it can be used to characterize compatibility (closedness of the set of graphs with respect to productions of the grammar). Second, together with L and R, they define the natural framework to study application conditions and graph constraints. Most importantly, nihilation matrices are the key idea to relate MGGs and complex analysis, swaps, etcetera (an introduction here).


I have said that the nihilation matrix just makes explicit some implicit information. We know that a production p transforms L into R. So in principle we should have all ingredients to know which are the forbidden elements in the image of the host graph G. Interestingly, the image of the nihil matrix K (which I will represent as Q) evolves according to the inverse of the production:

R = p(L) \longmapsto (R,Q) = (p(L),p^{-1}(K))

More on nihilation matrices can be found in Secs. 4.4 and 7.4 of the MGG book. Let's finish today with a nice cite from Karl Friedrich Gauss: It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

No hay comentarios:

Publicar un comentario en la entrada