Hi Johan:

>From johan@ccs.neu.edu Mon Jul  6 17:57:50 1998
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>cc: johan@ccs.neu.edu, boaz@ccs.neu.edu, dougo@ccs.neu.edu,
>        jayantha@ccs.neu.edu, mira@ccs.neu.edu
>Subject: Re: Doug = Johan? 
>From: Johan Ovlinger <johan@ccs.neu.edu>
>
>Karl gives a good summation of what I meant. 
>
>  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.)
>
>I used to-stop to disambiguate the case where there are several Qs in
>reachable from P in the CCG but only one in the ICG. The to-stop rule
>of thumb guarantees that the two graphs will agree.

I don't understand all you say but you will explain this in your
paper on a module system for APPCs.

>
>  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.
>
>I belive this theorem. The proof would be to look at the defintions of
>Paths[] and "expansion". Probably by induction.
>
>  Compatability checking is a minimum requirement; other constraints 
>  might have to hold for the APPC to work. 
>
>Yup. That's where semantic restrictions come in. However, they are
>probably undeciable in general. 

Can you give an example of a constraint a class graph must satisfy
relative to an APPC and which would be undecidable to check?
>
>Johan
>

-- Karl