======================================
Remarks about Cun Xiao's thesis (see the ftp directory 
ftp://ftp.ccs.neu.edu/pub/people/cunxiao/thesis.ps)

Checking whether a path is in PathSet

On pages 88 and 89, Cun gives an algorithm for checking whether
a path from Source(D) to Target(D) in a class graph G for a directive D
is in PathSet[G](D). The solution is very simple since we know that
we have a path from source to target in the graph G.
And that is what we have in the context of a traversal algorithm.

He gives a context-free grammar which defines a regular language.
He uses a geneal parsing algorithm for context-free grammars to give
an upper bound (cubic) on checking whether a path is in the path set.

So member testing in PathSet[G](D) can be done efficiently for paths
in the graph. This contrasts with a construction where we build a
non-deterministic automaton for accepting strings in PathSet[G](D).
Making the automaton deterministic might increase its size exponentially.

Stepping outside the regular expression and finite automata world
into the context-free world pays off and allows for an easy
description of an efficient algorithm for membership testing.