I agree with Mira's view that the second definition is better.

Johan has extricated the definition
of PathSet from the paper with Boaz.
Was that sufficient?

>       A strategy S1 is a substrategy of S2 iff S2 _contains_
>       a subgraph S3 such that S1 is homeomorphic to S3.
>
>That's more or less your formulation, right?
>How does that all sound?

Sounds great.

-- Karl

>From mira@ccs.neu.edu Mon Jun 29 09:25:06 1998
>Subject: Re: definition of substrategy
>To: lieber@ccs.neu.edu (Karl Lieberherr)
>Cc: johan@ccs.neu.edu (Johan Ovlinger), dougo@ccs.neu.edu (Doug Orleans),
>        mira@ccs.neu.edu, jayantha@ccs.neu.edu (Joshua C. Marshall)
>
>Hi Karl:
>
>I think your second definition of what a substrategy is
>
>> Definition:
>> A strategy S1 is a substrategy of strategy S2, if
>> there is a subgraph S3 of S2 such that
>> for all class graphs G:
>> PathSet[G](S1) is a subset of PathSet[G](S3).
>
>more accurate than the previous one
>
>> Definition:
>> A strategy s1 is a substrategy of strategy s2, if
>> for all class graphs G:
>> PathSet[G](s1) is a subset of PathSet[G](s2).
>
>The idea is that the paths generated by S1 may in general be
>shorter than those generated S2, since the source and the target of
>S1 could in general be internal nodes (other than source and target) of
>S2. So, we cannot compare  PathSet[G](s1) and PathSet[G](s2). Rather,
>a subgraph of S2 should exist such that
>
>> for all class graphs G:
>> PathSet[G](S1) is a subset of PathSet[G](S3).
>
>This is an intuitive explaination.
>I still need an exact definition of PathSet[G](S1). Can you give one? I
>printed out your paper with Boaz. Will read it in the hope to find the
>definition.
>
>Then, the theorem we are looking for would be something like:
>
>	A strategy S1 is a substrategy of S2 iff S2 _contains_ 
>	a subgraph S3 such that S1 is homeomorphic to S3. 
>
>That's more or less your formulation, right?
>How does that all sound?
>
>- Mira
>
>
>
>
>> Hi Doug and Mira:
>> 
>> you were both questioning:
>> 
>> does G contain a subgraph homeomorphic to H
>> 
>> versus
>> 
>> is H homeomorphic to G.
>> 
>> Below I argue that we want the first. Do you agree?
>> 
>> -- Karl
>> =========
>> Given strategies
>> 
>> S2 = {A -> B -> C -> D} with Source(S2)=A and Source(S2)=D
>> S1 = {B -> X -> C} with Source(S1)=B and Source(S1)=C
>> 
>> do we view S1 a substrategy of S2.
>> 
>> Yes, especially if we want to use strategies as interface strategy types.
>> 
>> Definition:
>> A strategy S1 is a substrategy of strategy S2, if
>> there is a subgraph S3 of S2 such that
>> for all class graphs G:
>> PathSet[G](S1) is a subset of PathSet[G](S3).      
>> 
>> This seems to correspond directly to subgraph homeomorphism:
>> 
>> instance: graph G = (V,E)
>> question: does G contain a subgraph homeomorphic to H, i.e.,
>>                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> a subgraph G'=(V',E') that can be converted to a graph isomorphic to H by
>> repeatedly removing any vertex of degree 2
>> and adding the edge joining its two neighbors?      
>> ===============================================
>> Hi Johan:
>> 
>> does the following theorem hold?
>> How would you prove it?
>> 
>> This is needed to decide whether a strategy is of a certain strategy
>> type.
>> 
>> -- Karl
>> =====================
>> 
>> Definition:
>> A strategy s1 is a substrategy of strategy s2, if 
>> for all class graphs G:
>> PathSet[G](s1) is a subset of PathSet[G](s2).
>> 
>> Theorem:
>> s1 is a substrategy of s2 iff PathSet[s1](s2) is not empty.
>> 
>> -- Karl
>> 
>
>