Higher-order and symbolic computation, 16(1-2):15-35, 2003.

Authors: Oege de Moor, David Lacey, and Eric van Wyk
>

Abstract

Given are a directed edge-labelled graph G with a distinguished vertex v0, and a regular expression P which may contain variables. It is required to compute substitutions phi (of symbols for variables), together with the set of vertices v such that all paths v_0 -> v are in phi(P). We derive an algorithm for this problem using relational algebra, and show how it may be implemented in the functional programming language Haskell. The motivation for the problem derives from a declarative framework for specifying compiler optimisations.

(PDF, PS)

BIBTEX:

           @article{hosc03moor, 
           author = "De Moor, Oege and Lacey, David and Van Wyk, Eric",
           title = "Universal regular path queries", 
           journal = "Higher-order and Symbolic Computation", 
           volume = "16",
           number = "1-2",
           pages = "15--35",
           year = "2003"}