From lieber@ccs.neu.edu  Thu Jan 16 10:54:44 2003
X-UIDL: 13l!!M`_"!8Ci!!pch!!
Return-Path: <lieber@ccs.neu.edu>
Delivered-To: lieber@ccs.neu.edu
Received: from ibm782cdt7 (bendel.ccs.neu.edu [129.10.118.162])
	by amber.ccs.neu.edu (Postfix) with SMTP
	id 76F7A6B74F; Thu, 16 Jan 2003 10:54:44 -0500 (EST)
Reply-To: <lieber@ccs.neu.edu>
From: "Karl Lieberherr" <lieber@ccs.neu.edu>
To: "Doug Orleans" <dougo@ccs.neu.edu>
Cc: "Lieber@Ccs.Neu.Edu" <lieber@ccs.neu.edu>
Subject: RE: intersection of strategies
Date: Thu, 16 Jan 2003 10:58:04 -0500
Message-ID: <LFELINLDMEAEKDCDKCMJMEIFCLAA.lieber@ccs.neu.edu>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0)
Importance: Normal
In-Reply-To: <15910.32219.65724.230956@vega.ccs.neu.edu>
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
X-Spam-Status: No, hits=-0.5 required=5.0
	tests=AWL,IN_REP_TO,QUOTED_EMAIL_TEXT,SPAM_PHRASE_01_02,
	      USER_AGENT_OUTLOOK
	version=2.43
X-Spam-Level: 
Status: RO
Content-Length: 1791

Hi Doug:

thank you for the clean graph-theoretic problem formulation
that Boaz and Raj can understand. Your idea at the end
looks good and if it is right it shows that general strategy
intersection is too time consuming.

Will you implement the approximate strategy intersection
discussed in the previous message?

Tomorrow at 9am is good.

-- Karl

>-----Original Message-----
>From: Doug Orleans [mailto:dougo@ccs.neu.edu]
>Sent: Thursday, January 16, 2003 4:40 AM
>To: lieber@ccs.neu.edu; boaz@ccs.neu.edu; raj@ccs.neu.edu
>Cc: dougo@ccs.neu.edu
>Subject: intersection of strategies
>
>
>Well, I think I'm going to give up on this, since the intersection of
>strategy graphs is probably exponential.  But, for the record, here's
>a better statement of the problem:
>
>Define paths(G,s,t) as the set of acyclic paths (node sequences) in
>graph G from node s to node t.
>
>Define traversals(G,S,s,t) as the set of p' in paths(G,s,t) such that
>there exists a path p in paths(S,s,t) such that p' is an expansion of p.
>(This is called S[G] in the paper.)
>
>Given two graphs S1 and S2, find a graph S such that for all graphs G,
>traversals(G,S,s,t) = intersect(traversals(G,S1,s,t), 
>traversals(G,S2,s,t)).
>
>Example:
>S1 = a -> x -> b        paths(S1,a,b) = {<axb>}
>S2 = a -> y -> b        paths(S2,a,b) = {<ayb>}
>
>
>        x -> y
>      /        \
>S = a            b      paths(S,a,b) = {<axyb>,<ayxb>}
>      \        /
>        y -> x 
>	
>
>I tried computing the product graph of S1 and S2, but I couldn't
>figure out how to map the nodes (S1xS2) to nodes in G.
>
>Hm, I just had an idea:
>
>  For each pair (p1,p2) in paths(S1,s,t) X paths(S2,s,t), let T be the
>  set of all topological sorts of p1 U p2.  Then S is the union of all T.
>
>Does this look correct?
>
>--Doug
>