Hi Mira:

>From mira@ccs.neu.edu Mon Jun 29 11:41:28 1998
>From: Mira Mezini <mira@ccs.neu.edu>
>Subject:  Re: definition of substrategy
>To: johan@ccs.neu.edu (Johan Ovlinger)
>Date: Mon, 29 Jun 1998 11:40:35 -0400 (EDT)
>Cc: lieber@ccs.neu.edu (Karl Lieberherr), mira@ccs.neu.edu,
>        dougo@ccs.neu.edu (Doug Orleans),
>        jayantha@ccs.neu.edu (Joshua C. Marshall)
>
>Hi Johan:
>
>> To: Mira Mezini <mira@ccs.neu.edu>
>> cc: lieber@ccs.neu.edu
>> Subject: Re: definition of substrategy
>> Date: Mon, 29 Jun 1998 09:35:14 -0400
>> 
>> Ok. That is a nice definition. Intuitively clear. I would be more
>> comfortable talking about languages, but if we stick to substrategies
>> (and their incident graphs) perhaps we can aviod some of the
>> difficulties I have encountered.
>> 
>> Johan
>
>Here is how Karl and Boaz define the way strategies express paths in
>object graphs (without constraint maps):
>
>Let {\em S}=(S, s, t) be a strategy, let G be a class graph, let N be a
>name map for S and G. Then
>
> {\em S}[G, N] = { X(p') | p' in P_G_(N(s),N(t)) and exists p in P_S_(s,t)
>                  such that p' is an expansion of N(p) }
>
>where P_g_(x,y) is the set of paths in graph g
>from x to y, X(p) is the mapping
>from class graph to object graph paths.

Thank you for extracting this.

Therefore, 

PathSet[G](S) = 
{ p' | p' in P_G_(N(s),N(t)) and exists p in P_S_(s,t)
                   such that p' is an expansion of N(p) }

>
>This confirms that the second definition of substrategies is the correct
>one, since the source and the target nodes of the strategies are important
>for defining their path sets. If we require PathSet[G](s1) to be a subset
>of PathSet[G](s2), we restrict substrategies to have the same target and
>source as the strategy.
>
>I would also like approaching the issue by talking about languages. I
>guess, the problem is that we cannot simply say:
>
>Pathset[G](S) = L(G) intersect L(S) 
>
>because we are only interested in the language generated by S wrt "G's
>alphabet". So, we need to be a bit more precise by considering 
>something like L(S-G). 
>L(S-G) is the language generated by S over the alphabet V where V is the
>set of nodes of G: 
>   G = (V, E, L)
>
>Now, we know that L(G) intersect L(S-G) = L(S-G). Thus, based on the
>definition of substrategies:
>
>> 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).
>
>we would have directly that S1 is a substrategy of S2 iff:
>there is a subgraph of S2, S3, such that:
>
>   L(S1-G) <= L(S3-G)
>
>
>Does that make any sense?????

Yes, this makes sense to me in the following way:

Pathset[G](S) = regular set of all paths from source to target
  of traversal graph of G and S.
and you use Pathset[G](S) = L(S-G)

We can view PathSet[G](S) as the intersection of two regular sets.
The first one is the regular set constructed from G.
We essentially view G as an NFA which has node names
from G as edge labels.
The second one is the regular set constructed from S and the name
map from S to G.

Therefore, Pathset[G](S) = L(T1(G)) intersect L(T2(S,N))

where T1 and T2 are suitable transformations.

Johan: please can you write down those transformations in a general form!

>
>The issue pointed out by Karl:
>
>> what is a general algorithm to map strategy graphs into equivalent
>> regular expressions?
>
>remains.

Yes. Johan will write this down.

>
>Also, the name mapping function needs to be involved in the definitions of
>the languages.

Yes.

>
>
>- Mira
>

-- Karl

>
>>
>>> Subject: Re: definition of substrategy
>>> To: lieber@ccs.neu.edu (Karl Lieberherr)
>>> Date: Mon, 29 Jun 1998 09:24:14 -0400 (EDT)
>>> 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
>
>