Compatability in AP

In [PXL95] compatability is defined as:
(using now the strategy graph terminology):
A strategy S is compatible with a class graph G if for any substrategy S' of S there is a path in G from Source(S') to Target(S').

The intuition is that each "piece" of the strategy define a path in the class graph. This means that the strategy "matches" the class graph in terms of paths; we can embed the paths in the strategy graph in the paths in the class graph.

To check for compatability is easy: check each substrategy which is only a single edge A->B whether it defines a non-empty path set. The reason why it is enough to check only the single edge strategies is that the path set of each substrategy is made up of the path sets of the single edge strategies. A substrategy can have an empty path set iff one of the single edge substrategies has an empty path set.

Therefore we define now:
A strategy S is compatible with a class graph G if for all single edge sub strategies S' of S there is a path in G from Source(S') to Target(D'). 

Or in more generic terms:
A graph G2 is Johan-compatible with a graph G1 if for all edges P->Q of G2 there exists a path p' in Path[G1](N(P),N(Q)). (Johan said that from P to-stop Q must define an non-empty path set. But P to Q is non-empty iff P to-stop Q is non-empty.)

The benefit of Johan's compatability definition is that it works for multiple source and target strategies too. However, we would like to verify that the new definition is identical to the old one for the single source and single target case.
By old one I mean the following definition given by Doug Orleans: G1 is Doug-compatible with G2 if for all paths p in Paths[G2](s,t) there exists a path p' in Path[G1](N(s),N(t)) such that p' is an expansion of p.

Theorem Compatibility Equivalence: (i)If G1 and G2 are Doug-compatible then they are Johan-compatible.
(ii) If G1 and G2 are Johan-compatible and G2 is single source and single target then they are Doug-compatible.

Johan: can you prove this theorem or find counter examples?

Implication: In our papers we should use Johan-compatible since it is easier to understand and it is immediate how to check for compatibility.

To work with APPCs we use the compatability concept in two stages: at the adaptive level we check that the interface class graph conforms to each strategy. At the instantiation level we check that the concrete class graph conforms to the interface class graph.
Compatability checking is a minimum requirement; other constraints might have to hold for the APPC to work.