composition and compatibility

composition and compatibility of sequences

So far I have introduced sequentialization (the productions inside a sequence are applied one after the other). Today I will scratch on parallelism, but first we need to introduce composition of productions.

Consider a sequence. Its composition is just the composition of the productions. Thus, we obtain a single production that performs the same actions than the whole sequence. The natural question that arises with composition is: What do we need sequences and concatenation for?. There are some differences that make composition and sequentialization pretty different concepts.

The first is that of intermediate states: Sequences of productions generate intermediate states while their composition does not  (it is a single production). Not only that, but the final state may differ in both cases. Think of a sequence that first deletes and then adds one node. Had the node any dangling edge, it is deleted by some epsilon-production. However, its composition does not touch the node, so it does not delete those edges.

If two productions are sequentially independent, it does not matter the order of their application, so they can be executed in parallel. But in the MGG book, Chap. 6, it is proved that advancing (or delaying) one production two positions inside a sequence in a single step is weaker (less demanding) than advancing one position and then another position.


In general, if two sequences are going to be applied in parallel, then every production in the first sequence needs to be sequentially independent with respect to all productions in the second. Previous comments weaken this, so it is possible to execute independent subsequences in parallel. See Sec. 5.4 of the MGG book.

Today's post ends quoting Edsger Dijkstra: Elegance is not a dispensable luxury but a quality that decides between success and failure.