Dear Boaz:

thank you for the revised paper. I basically like the revisions but
have some questions that I will discuss in separate messages.

The paper discussion reachable from:
http://www.ccs.neu.edu/research/demeter/biblio/strategies.html
makes the connection to automata theory. I think that something like the
following should be put into the paper.

P>
Comparison with automata-theoretic algorithms:

<P>
The paper introduces two algorithms:
Algorithm 1, better called Traversal Graph Algorithm and
Algorithm 2, better called Traversal Method Algorithm.
An intuitive understanding of those algorithms from
an automata-theoretic point of view can be obtained
by simplifying the problem and considering only class graphs
without subgraph edges. The Traversal Graph Algorithm now
becomes the cross-product algorithm for NFAs.
See
<A href="
http://www.ccs.neu.edu/research/demeter/papers/boaz-jacm/NFA
">
NFA algorithms and AP algorithms</A>
for examples. It is necessary to encode both the class graph and the
strategy graph in a certain way to see the connection to NFA intersection.

<P>
It is important to note that the Traversal Graph Algorithm is a non-trivial
application of the NFA intersection algorithm. The Traversal Graph Algorithm
deals 1. with general class graphs, 2. with negative information in the
strategy graph edges 3. with a controlled minimization of the automaton
without resorting to a general purpose automaton minimizer that
would destroy the desired structure.

<P>
The Traversal Method Algorithm also has a connection to
NFA intersection at least from a theoretical point of view: The
intersection of the traversal graph and an object graph tells
us whether there is any traversal at all.
The Traversal Method Algorithm can be viewed as an application
of an NFA simulator. However, again there are significant differences.
The Traversal Method Algorithm deals with 1. general class graphs,
2. the objects traversed are trees, not strings

-- Karl