To: lieber

From dougo@ccs.neu.edu  Wed Nov 22 03:54:10 2000
From: Doug Orleans <dougo@ccs.neu.edu>
Date: Wed, 22 Nov 2000 03:54:01 -0500 (EST)
To: Mitchell Wand <wand@ccs.neu.edu>
Cc: Karl Lieberherr <lieberherr@ccs.neu.edu>, dem@ccs.neu.edu
Subject: Re: Navigating in Object Graphs (version of 11/17/00)

Mitchell Wand writes:
 > Procedure search(o,Q'):
 > 
 > 1.  If o does not have type class(q) for any q in Q', then for each q
 >     in Q', and each e in POSS(class(o),class(q)),
 >     search(o.e, Q').  {We are not at a point on the subsequence}
 > 
 > 2.  If o has type class(q) for some q in Q' \intersect QF, then visit(o).
 > 
 > 3.  Otherwise let Q'' = {q in Q' | o does not have type class(q)} u
 >     {q'| exists q in Q' s.t. o has type class(q) and S(q,q')}.  Then
 >     search(o,Q'').

Aha, this algorithm accepts a strategy graph with an edge from a
superclass to a subclass (or vice versa), i.e. you're not required to
look at POSS in each iteration (you might go from step 3 directly to
step 3).  Karl, this satisfies my objection from last week's seminar.

Also, I believe the set of states Q' that you carry along maps exactly
onto the token-set T' of Boaz's algorithm 2, except I think T' is
roughly a set of edges in the strategy graph while Q' is a set of
nodes in the strategy graph.  The distinction probably only matters
when you take into account the constraint map, which maps strategy
graph edges to predicates.

--Doug