To: dougo@ccs.neu.edu, lieber@ccs.neu.edu
Subject: Re: is this relevant?

Hi Doug:

I was thinking this morning as follows:

A traversal strategy s1 * s2 * ... * sn, where * is intersection
might result in a traversal graph of exponential size
when applied to a class graph.

To implement (s1 * s2 * ... * sn).cd
You propose to compute TG(s1,cd), TG(s2,cd), and employ
all those traversal graphs during the traversal.

I think that the following approximation is best:

TG(s1, ... CD(TG(sn-1, CD(TG(sn,cd))))...)

This simulastes what we have done so far in a different syntax
and we view this as the definition of our intersection operation.

Advantages:
no exponential blow-up.
we could later introduce the standard intersection operation
  if it is really needed and can be done efficiently.

Do you think this will work?

-- Karl


>From dougo@ccs.neu.edu  Wed Jan 15 01:28:00 2003
>Delivered-To: lieber@ccs.neu.edu
>From: Doug Orleans <dougo@ccs.neu.edu>
>Date: Wed, 15 Jan 2003 01:27:58 -0500 (EST)
>To: lieber@ccs.neu.edu (Karl Lieberherr)
>Subject: Re: is this relevant?
>
>Karl Lieberherr writes:
> > Intersection of regular relations is not regular. See below.
>
>Right, but a strategy graph corresponds to a regular language, not a
>regular relation-- it's an automaton, not a transducer; it doesn't
>output any symbols, it just recognizes sentences.
>
>I played around with translating a strategy to an NFA, then
>intersecting two NFAs, then turning the result back into a strategy.
>Along the way I think I managed to rediscover Boaz's traversal graph
>algorithm...  I think there must be a simpler way to do it.  I'm going 
>to try different ways of computing the graph product to see if any of
>those work.
>
>It may turn out that the easiest thing to do is, given an intersection 
>of two strategy graphs and a class graph, compute both traversal
>graphs and then run them both in parallel like in Algorithm 3.  But it 
>would be much more convenient if we could compute a single strategy
>graph that is equivalent to the intersection.  I'll spend another day
>on it before moving on.  I've already added adaptive methods to DAJ,
>but I can't get rid of ClassGraph declarations until we can handle
>strategy intersection.
>
>--Doug
>