Higher-Order and Symbolic Computation, 16(1/2)15-35
Universal Regular Path QueriesOege de Moor, Oxford University Computing Laboratory
David Lacey, Oxford University Computing Laboratory
Eric Van Wyk, University of Minnesota
|
Abstract: Given are a directed edge-labelled graph G with a
distinguished node n0, and a regular expression P which may contain
variables. We wish to compute all substitutions S (of symbols for
variables), together with all nodes n such that all paths n0 --> n are
in S(P). We derive an algorithm for this problem using relational
algebra, and show how it may be implemented in Prolog. The motivation
for the problem derives from a declarative framework for specifying
compiler optimisations.
Keywords: program transformation, regular algebra, program analysis, query languages |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)