the very basics II

The very basics of graph dynamics: completion and compatibility


A production in MGG specifies some Boolean matrix operations. The first thing to do is to "complete" the matrices so the Boolean operations make sense. This is not a trivial fact because not only the number of elements in the matrices may differ but also their ordering. Somehow it has to be decided which nodes are the same in different graphs, respecting types. Notice that this is one source of non-determinism unless all types are different.


This property is closely related to the matching problem: Given a host graph (initial state to which the grammar is going to be applied), select the places where the productions are going to be applied.

Notice there is still another source of non-determinism in MGGs: A means to select the following production to be applied. This sort of non-determinism is avoided by providing a sequence of productions, which is nothing but a set of productions to be applied in a given order.

Completion is necessary to perform the algebraic operations and we will always assume in MGGs that it has been performed somehow. More on this in Sec. 4.2 of the MGG book. The two sources of non-determinism commented above are relevant if we consider MGG as a model of computation, which I will do in future posts.

Another algebraic need is compatibility. We give the adjacency matrix to specify the edges of a graph, which implicitly contains the nodes of the graphs. As productions may act on nodes independently, a vector of nodes is also given and we have to be sure that the adjacency matrix and the vector of nodes are compatible, i.e. they have the same nodes (no edge is incident to a node that does not belong to the graph). A production is said to be compatible if it outputs a compatible graph starting out of a compatible graph. A similar definition of compatibility is given for sequences in the MGG book (intermediate states have to be compatible).

Compatibility is in essence well-formedness of graphs.

I finish today with a quote from Richard Feynman: "The worthwhile problems are the ones you can really solve or help solve, the ones you can really contribute something to. ... No problem is too small or too trivial if we can really do something about it."