Hi Jeff:

I think that the analogy below is worthwhile to work
out in detail.

Pengcheng has already a translation from p to s.

Is there a project in the theory of computation class?
This would be a good one.

-- Karl
March 14, 2004

PCDS and regular expressions

Analogy:

strategy s / class graph g / object graph o
all three are automata
s product g = traversal graph t
o product t = object graph slice
s is satisfiable if there exists a g and an o
so that (s product g) product o is non-empty

See:
http://www.ccs.neu.edu/research/demeter/seminar/1998/feb10/trav-theory.ppt


pcd p / call graph c / call tree d
all three are automata
p product c = XYZ graph x
d product x = set of nodes in d
d is satisfiable ...

=================
Hi Boaz:

our strategy notation looks more and more to what we had
3 years ago with the big difference that we have now a fast implementation.

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.

The enhanced regular expressions can also express some things that I can't
see how to express with the operators, such as paths from A to B that
don't visit an A or B node except at the start and end:

  A.(any*).B \cap not(A.any.(any*).(A \cup B).(any*).any.B)

Since the enhanced regular expressions are equivalent to DFAs (enhanced
with the ability to sense node types), it would be an interesting exercise
to find a set of operators that could capture any regular expression.