The currently best solution for the NP-completeness of the
"possible graph-semantics" and the currently wrong implementation
in DAJ is as follows:

We allow intersection only at the outermost level
(this can probably be generalized) and we assume that the
number of intersection operators is small, say less than a constant, say 3.

To implement intersect(s1,s2) for class graph G, we compute the two
traversal graphs TG(s1,G) and TG(s2,G) and compute the product
of those graphs. Emptyness of the pathset can now be determined
by a simple reachability computation in the product graph.

Because we assume that we have a constant number of intersections,
the state explosion problem is bounded.

Indeed, with a constant number of intersections, the semantics
become polynomial again.

DAJ users will need to know that intersection is expensive.

I discussed this with Doug, Theo, and Mitch.

As a corollary of Ravi's reduction we can claim:
REGULAR PATH WITH INTERSECTION is NP-complete.

Definition:
REGULAR PATH WITH INTERSECTION 
Input: DAG G with distinguished nodes s and t, 
regular expression R using &,|,* and concatenation
Question: Is there a path from s to t satisfying R.

Idea:

(x1 + x2)*!x1*!x2 we translate to:

(s any* x1 any* t | s any* x2 any* t)&
(s any* x1_n any* t) &
(s any* x2_n any* t)

Class graph: see Ravi's construction.

As another corollary to Ravi's reduction we can claim:

We parameterize the semantics of traversals by a
traversal strategy notation SN for which we use
several instantiations. We ask the question: Q(SN):
is the path set empty for given strategy s in SN and class graph g. 

Q({join, merge}) polynomial by TOPLAS 2004
Q({join, merge, intersection}) NP-complete by Ravi's reduction
Q({join, merge, negation}) NP-complete by Ravi's reduction
  because we can simulate intersection using negation and merge:
  !(!a + !b) = a*b
Q({join, merge, negation of joins only}) polynomial by TOPLAS 2004

Greetings from Switzerland,
-- Karl

==============================
Ravi discovered a hole in the traversal semantics we use in the presence of intersection
in the strategies. Intersection is implemented in DAJ and is a central feature of DAJ.
We basically use intersection to eliminate undesired nodes and edges in a modular way.

Remember the Mitch-semantics for traversals: Traverse that edge if P holds: 
Does there exist an object containing a path satisfying the strategy? 

Ravi's important observation is that in the presence of intersection P becomes NP-complete.
http://koods1.ccs.neu.edu/traversal-wiki/index.php/SatisfiabilityHardness

(password K@rl)

See:
pages 42 and up in:

-rw-r--r--   1 lieber   faculty   141096 Jul 16 14:53 intersection+negation1.pdf
-rw-r--r--   1 lieber   faculty   259584 Jul 16 14:51 intersection+negation1.ppt

/proj/adaptive/www/design-decisions/traversal-strategies/intersection>

for a discussion and possible solutions.

How would you resolve this?

-- Karl