Hi Ravi:

Another difference is that graph strategies are more general
than the regular expressions below.

-- Karl
============================
From lamping@parc.xerox.com Thu Aug 31 13:33:57 1995
Subject: Re: Boolean and Regular

We seem to be converging, but I still think that enhanced regular
expressions can express all of the operators.  Here is the enhanced regular
expression language from a while back:

Atomic expressions:

   A    The empty traversal at class A
   lnk  a link of type lnk ("any" is a special case of any link type)

For combining expressions, the usual regular expression crowd:
   .     concatenation
   \cap  intersection
   \cup  union
   *     repetition
   not   negation

Note that A is like an empty string; the traversal that just sits at class
A.  As with all empty strings, A.A = A


Here are the operators from the Karl's last message, with a translation
into enhanced regular expressions:

[A,B]			A.any*.B
through edges           any*.lnk.any*
bypassing edges         not(any*.lnk.any*)
through vertices        any*.A.any*
bypassing vertices      not(any*.A.any*)
d1 join d2              [d1].[d2]
d1 merge d2             [d1]\cup[d2]
d1 intersect d2         [d1]\cap[d2]
not d1                  not([d1])

where [x] is the translation of x into regular expressions.

Of course, \cap is not strictly necessary, as it can be expressed in terms
of \cup and not.  Furthermore, with distribution, not can be pushed down to
leaves.