application conditions II

application conditions and sequences

When an application condition (AC) is defined, we may face some problems. These problems can be described informally as follows: There is at least one graph that satisfies the AC (the AC is consistent); the AC is not a fallacy, i.e. false in all possible escenarios (the AC is coherent) and the AC describes some simple digraph (the AC is compatible).

Coherence typically fails because the AC asks for some element to be present and not to be present in the host graph (the graph the production is going to be applied to). Non-compatibility deals with internal structural inconsistencies. Consistency is concerned with applicability. It is proved in Chap. 7 of the MGG book that consistency is equivalent to compatibility plus coherence.

It is possible to use two operators (closure and decomposition) to transform any application condition into an equivalent sequence or set of sequences. In my opinion this is the main (unexpected) result of Chap. 7. This theorem has important consequences:

1. All the machinery developed for sequences can now be applied to graph constraints and ACs.
2. Through sequential independence, preconditions can be transformed into equivalent postconditions and viceversa.
3. It is another example of an operator equivalent to a (set of) sequence(s). Other examples are the marking operator, the matching and the operator dealing with epsilon-productions.

In fact more can be said: Any precondition is equivalent to some postcondition and viceversa. This is a quite strong statement. It says that ACs are "delocalized" inside the production. Again, more can be said: Application conditions can be moved from one production to another inside sequences. So this "delocalization" happens in sequences as well.

From a more practical point of view, ACs can be used to allow MGG to tackle with multidigraphs with no major modification of the theory. This solves one of the main practical drawbacks of MGG (the other one being relabelling, which I will address in a future post). They can also be used to study other models of computation as particular cases of MGG, such as Turing Machines and Boolean Circuits.

I cite Aristotle today: The whole is more than the sum of its parts.