**Subject: **Regular Path Queries

**From: **Karl Lieberherr (*lieber@ccs.neu.edu*)

**Date: **Wed Jul 24 2002 - 16:04:15 EDT

**Reply****Next message:**Annie Liu: "Regular Path Queries"**Previous message:**Barry Cedergren: "Mobile DJ Services - action requested"**Next in thread:**Annie Liu: "Regular Path Queries"**Reply:**Annie Liu: "Regular Path Queries"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

Hi Annie:

I saw your interesting abstract in the NEPLS symposium announcement

on regular path queries (attached below).

We work on related problems as summarized here:

The object structure concern is about how objects are structured and it is

typically expressed by a class graph (e.g., a UML class diagram). A suitable

abstraction of a class graph for programming is a non-deterministic finite

state automaton (NFA) that induces traversals in the objects belonging to the

class graph. We write our programs with respect to a NFA. The NFA

describes the important properties of the structural concern that are relevant

to the current concern that is about implementing a specific behavior. How

can we program against the NFA? A natural way is to annotate the NFA

with code that is executed before entering a state and before leaving a state

and before and after state transitions. The code defined in the NFA is

executed as the objects of the class graph are traversed. It is useful to keep

the code annotations defined in the NFA separate from the NFA itself

because they address different concerns that might be separately reusable.

Therefore, programming in this style uses a triple: (CLASS GRAPH, NFA,

NFA ANNOTATION). Sometimes, this triple is called: (CLASS GRAPH,

TRAVERSAL SPECIFICATION, VISITOR).

Relevant papers are:

TOPLAS 1:

http://www.ccs.neu.edu/research/demeter/biblio/compile-ap.html

TOPLAS 2:

http://www.ccs.neu.edu/home/dougo/papers/strategies/*.pdf

With Mitch Wand:

http://www.ccs.neu.edu/research/demeter/papers/new-strategy-semantics/

Can your algorithm derivation techniques als be applied to

our three layer scenario?

How can we compute the traversal graph incrementally?

Do your techniques apply?

One of our favorite regular expressions is:

A any* B meaining: Given an A-object, find all B-objects the A-object contains.

any is the set of all nodes in the graph.

Best regards,

-- Karl

==============

Annie's abstract:

Regular path queries are a way of declaratively specifying program

analyses as a kind of regular expressions that are matched against

paths in graph representations of programs. These and similar queries

are useful for other path analysis problems, such as model checking,

as well. This talk describes the precise specification, derivation,

and analysis of an efficient algorithm and implementation for solving

regular path queries. We start with a specification that corresponds

rather directly to the English description of the problem, apply rules

that capture some common knowledge at a high level, and then apply

program transformations that are centered around Paige's finite

differencing (i.e., incremental computation) techniques. This formal

derivation allows us to analyze the time and space complexity of the

implementation precisely in terms of size parameters of the graph and

the deterministic finite automaton that corresponds to the regular

expression. In particular, the time and space complexity is linear in

the size of the graph. We also prove that the problem is

PSPACE-complete in terms of the size of the regular expression. In

applications such as program analysis, the size of the graph may be

very large, but the size of the regular expression is small and can be

considered a constant.

**Next message:**Annie Liu: "Regular Path Queries"**Previous message:**Barry Cedergren: "Mobile DJ Services - action requested"**Next in thread:**Annie Liu: "Regular Path Queries"**Reply:**Annie Liu: "Regular Path Queries"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b28
: Wed Jul 24 2002 - 16:04:20 EDT
*