Hi Boaz:

do you agree with:

 S1 <= S2 iff PathSet[S1](S1) = PathSet[S1](S2)

I sthis the same statement we had on Friday?

-- Karl

===============
Hi Boaz:

thank you for pointing out that it is not enough that 
PathSet[S1](S2) be non-empty. Your off-hand remark brought
me to the following:

	S1 <= S2 iff PathSet[S1](S1) is a subset of PathSet[S1](S2).

Unless S1 is empty,  PathSet[S1](S1) cannot be empty and therefore
PathSet[S1](S2) is non-empty.

Since S1 is a substrategy of S2, S1 is a bigger graph so we use
it on both sides to normalize the comparison.

Also, since the paths in S1 must be included in PathSet[S1](S2)
all those paths must satisfy the constraints of S2.

How does this look?

The reason for having such a theorem is to have an efficient
algorithm to check the substrategy property.

To check whether one path set is a subset of another path set,
we compute the traversal graphs for both path sets and
solve the subgraph isomorphism problem but with
the required bijection already given through the node labels.

Or do you have a better way to check the substrategy property?

-- Karl

>From boaz@eng.tau.ac.il Tue Jun 23 09:50:52 1998
>From: Boaz Patt-Shamir <boaz@eng.tau.ac.il>
>To: Karl Lieberherr <lieber@ccs.neu.edu>
>cc: boaz@eng.tau.ac.il
>Subject: substrategy
>
>The conjecture is false.
>Intuitively: S1 <= S2 ("<=" stands for "is a substrategy of") if all
>paths satisfying the constraints of S1 satisfy also the constraints of
>S2 (assuming a fixed name-map). But for the PathSet[S1](S2) to be
>non-empty all that is needed is that ONE of the paths in S1 satisfies
>the constraints of S2.
>Formally: Consider the following graphs.
>(S1)
>A: B,C.
>B: D.
>C: D.
>D: .
>(S2)
>A: B,E.
>B: D.
>E: D.
>D: .
>
>The source is A and the target is D in both.
>Clearly, neither S1 <= S2 nor S2 <= S1, but both
>PathSet[S1](S2) = PathSet[S2](S1) = {(A,B,D)}.
>
>Off-hand, I think that the theorem you're after should say something
>like  
>	S1 <= S2 iff PathSet[S1](S2) is a subset of PathSet[S2](S2).

	S1 <= S2 iff PathSet[S1](S1) is a subset of PathSet[S1](S2).

>
>Boaz
>
>
>Karl Lieberherr writes:
> > Hi Boaz:
> > 
> > Have a very good trip to the US and Mexico. Please call
> > when you are here.
> > 
> > Does the following theorem hold?
> > 
> > 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
>