From lieber@ccs.neu.edu Tue Nov 7 17:10:04 2000 Return-Path: Received: from bendel (bendel.ccs.neu.edu [129.10.118.162]) by amber.ccs.neu.edu (8.10.0.Beta10/8.10.0.Beta10) with SMTP id eA7M9l109496; Tue, 7 Nov 2000 17:09:47 -0500 (EST) Message-ID: <001601c04907$d738da80$a2760a81@ccs.neu.edu> From: "Karl Lieberherr" To: Cc: "Boaz Patt-Shamir" Subject: even simpler semantics of strategies Date: Tue, 7 Nov 2000 17:12:33 -0500 Organization: Northeastern University MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0011_01C048DD.EB4F7800" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.00.2314.1300 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 Status: R Content-Length: 4306 This is a multi-part message in MIME format. ------=_NextPart_000_0011_01C048DD.EB4F7800 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I was thinking more about a direct explanation of strategies in terms of = object graphs based on our discussion at the seminar last week and = Mitch's paper on it.It turns out that the semantics is very simple. The = object graph slice consists of the subgraph of the object graph touched = by paths leading to a target and the early terminated paths as described = below. This is the simplest explanation of traversals we have. The automata = theory is only needed for efficient implementation. The concepts needed = are: strategy graph, class graph, object graph, path expansion, node = substitution, maximal prefix of a path satisfying a reachability = property in class graph. -- Karl A simple view of traversals in terms of strategies and object graphs When a traversal reaches a target node (a node whose class is t) in the = object graph, the path traversed from the source, with suitable = substitution of subclasses by superclasses, must be an expansion of an = s-t path in the strategy graph. s is the source and t is the target of = the strategy.=20 A simple view of traversals: class graph prevents unnecessary traversals When a traversal reaches a final node in the object graph without being = at a target, the path traversed from the source, with suitable = substitution of subclasses by superclasses, must be a prefix of an = expansion of an s-t path in the strategy graph. The prefix is the = longest prefix such that there is still a possibility of success as = determined by the class graph. Assume class graph is flat: subclass and = construction edges only. ------=_NextPart_000_0011_01C048DD.EB4F7800 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

I was thinking more about a direct=20 explanation of strategies in terms of object graphs based on our = discussion=20 at the seminar last week and Mitch's paper on it.It turns out that the = semantics=20 is very simple. The object graph slice consists of the subgraph of the = object=20 graph touched by paths leading to a target and the early terminated = paths as=20 described below.

This is the simplest explanation of = traversals we=20 have. The automata theory is only needed for efficient implementation. = The=20 concepts needed are: strategy graph, class graph, object graph, path = expansion,=20 node substitution, maximal prefix of a path satisfying a reachability = property=20 in class graph.

-- Karl

A simple view of traversals
in terms of strategies and object=20 graphs

When a traversal reaches a target node (a node whose = class is t)=20 in the object graph, the path traversed from the source, with suitable=20 substitution of subclasses by superclasses, must be an expansion of an = s-t path=20 in the strategy graph. s is the source and t is the target of the = strategy.=20

A simple view of traversals: class graph prevents unnecessary=20 traversals

When a traversal reaches a final node in the object graph without = being at a=20 target, the path traversed from the source, with suitable substitution = of=20 subclasses by superclasses, must be a prefix of an expansion of an s-t = path in=20 the strategy graph. The prefix is the longest prefix such that there is = still a=20 possibility of success as determined by the class graph. Assume class = graph is=20 flat: subclass and construction edges=20 only.

------=_NextPart_000_0011_01C048DD.EB4F7800-- From wand@ccs.neu.edu Tue Nov 7 17:30:17 2000 Return-Path: Received: from alnilam.ccs.neu.edu (wand@alnilam.ccs.neu.edu [129.10.117.107]) by amber.ccs.neu.edu (8.10.0.Beta10/8.10.0.Beta10) with ESMTP id eA7MU9110634; Tue, 7 Nov 2000 17:30:09 -0500 (EST) Received: (from wand@localhost) by alnilam.ccs.neu.edu (8.10.0.Beta10/8.10.0.Beta10) id eA7MU9F02945; Tue, 7 Nov 2000 17:30:09 -0500 (EST) From: Mitchell Wand MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <14856.33393.203284.2068@alnilam.ccs.neu.edu> Date: Tue, 7 Nov 2000 17:30:09 -0500 (EST) To: "Karl Lieberherr" Cc: , "Boaz Patt-Shamir" Subject: even simpler semantics of strategies In-Reply-To: <001601c04907$d738da80$a2760a81@ccs.neu.edu> References: <001601c04907$d738da80$a2760a81@ccs.neu.edu> X-Mailer: VM 6.70 under Emacs 19.34.1 Status: R Content-Length: 2246 Karl wrote: > A simple view of traversals in terms of strategies and object graphs > When a traversal reaches a target node (a node whose class is t) in > the object graph, the path traversed from the source, with suitable > substitution of subclasses by superclasses, must be an expansion of > an s-t path in the strategy graph. s is the source and t is the > target of the strategy. > A simple view of traversals: class graph prevents unnecessary traversals > When a traversal reaches a final node in the object graph without > being at a target, the path traversed from the source, with suitable > substitution of subclasses by superclasses, must be a prefix of an > expansion of an s-t path in the strategy graph. The prefix is the > longest prefix such that there is still a possibility of success as > determined by the class graph. Assume class graph is flat: subclass > and construction edges only. I think it would be better to formulate this without reference to the strategy graph. The key construct is POSS(c1, t) = those edges e s.t. there is an object graph O (consistent with the class graph C), an object o1 of class c1, an object o2 of type (not class) t, and a path in O from o1 to o2 such that the first edge in the path is e. The object graph slice starting with o1 is the slice built by following the edges POSS(class(o),t) starting with o = o1 and continuing until every path terminates at an object of type t. If the traversal is [to t1 to t2 to t3 ..], then the object graph slice is constructed recursively as in the last few para of the same note. This determines the slice. The issue of which visitors are executed, and when, is a separate issue: you might want the visitors executed as you build the slice (either depth-first or breadth-first), in which case you'd wind up executing visitors on paths that do not reach the target, or you could accumulate the path as you go, and execute the visitors only when you reach the target. This does *not* require that the class graph be flat. The sets POSS(c, t) can be computed by transitive-closure operations, as per my note. Of course, I may be misunderstanding the notion of a strategy graph, in which case we may be in violent agreement. --Mitch