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.