Hi Ravi:

this is also for our agenda tomorrow at 10 am in my office.

The other agenda items are:

Rewrite of journal submission.

NSF proposal topics.

-- Karl

Regular expressions over graphs/instances

We have a rooted directed graph G, a regular expression r.

Given G, r we ask: Is there a "path" in G
satisfying r.

By "path" we mean:
1. A normal path from the root (that is what we have studied so far).

2. Now we are also interested in history paths:
Those are paths consisting of a partial depth-first traversal of the graph.
Those paths have forward and backward edges.
(Earlier we did not have backward edges.)

QUESTION:
How are our results affected by the "history path" concept.

In history paths we distinguish between "before A" and "after A"
events for a node A. So a regular expression might be:
before A (before B)* after A

The benefit of history paths is that we can make the aspects higher level.

A good way to declare the regular expressions is to use a two step
approach: 1. Define the set of events of interest and then 2. to 
define the regular expression using a subset of those events.
This way we "bypass" certain events.

-- Karl