sequentialization and sequential independence

sequentialization and sequential independence

Assume we are given a sequence of productions. Recall that a sequence is just an ordered (finite) set of productions. A natural question is whether some production can be applied before (advanced) or after (delayed) its current position without altering the result of the sequence. In essence, this is sequential independence.
Suppose that our sequence is made up of two productions p₂;p₁ (p₁ is applied before p₂ by convention). In this case if p₂ can be advanced -- or equivalently p₁ can be delayed -- and the new sequence p₁;p₂ has the same output as the original, then we say that p₂ is sequentially independent of p₁ (or vice versa).

Sequential independence is an important concept, both from the theoretical and the practical points of view. Theoretically, it extends commutativity to an arbitrary (though finite) amount of elements. Practically, it is closely related to parallel execution of tasks (a future post on this).

Chapter 6 of the MGG book addresses independence for sequences and for derivations (recall that a derivation is a sequence applied to an initial graph). Sufficient conditions for moving productions are stated and proved. In the literature, in order to test sequential independence for jumps larger than a single position, the production is checked to be sequentially independent with respect to every single production in the jump. One interesting result proved in the MGG book is that this is much more restrictive than what a direct jump actually needs.

Sequential independence can be characterized in terms of coherence (see this post or Chap. 4 in the MGG book) and congruence (I will write a post on it; it is addressed in Sec. 6.1 of the MGG book).

Today I quote Henri Poincaré: to doubt everything or to believe everything are two equally convenient solutions; both dispense with the necessity of reflection.