derivations III

derivations and direct derivations. Part III (epsilon-productions)

Today I touch on dangling edges. Let p be a production that specifies the deletion of one node (the LHS -- left hand side -- is made up of a single node and its RHS is empty). Suppose the production is applied to a graph with no isolated nodes. What happens with the edges that are incident to the node that p deletes?

There are two possibilities: Either the production can not be applied or every edge incident to the node that is going to be deleted is also deleted. Let us call those grammars fixed grammars and floating grammars, respectively.

In the categorical approach fixed grammars correspond to the DPO approach and floating grammars to the SPO approach.This is precisely the main difference between them. The pushout construction takes care of dangling edges in the SPO approach and the double pushout construction (DPO approach) does not allow the application of a production if any edge is going to become a dangling edge.

MGG is a floating grammar (this topic is addressed in detail in Sec. 5 of the MGG book). This is achieved using one operator, T. The basic idea is to enlarge the production p in order to include (to delete) any potential dangling edge. As it always happens up to now in MGG, an operator turns out to be equivalent to a certain sequence of productions. In case of dangling edges T(p) is equivalent to a sequence of two productions p;p_{e , where} p_e (epsilon-production or e-production) deletes any potential dangling edge (p_e is applied before p). If a fixed grammar is preferred, it is enough to make T be the identity operator (compatibility is an application condition that MGG has for free).

It remains to guarantee that p and p_e will be applied in the same place of the graph (recall non-determinism). To this end MGG uses marking, which is introduced in Sec. 5.2 of the MGG book.

Today I quote Thales. In my opinon, honesty is a must: I will be sufficiently rewarded if when telling it to others you will not claim the discovery as your own, but will say it was mine.