Universal regular path queries

Oege De Moor, David Lacey, Eric Van Wyk

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


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 φ (of symbols for variables), together with all nodes n such that all paths n0 → n are in φ(P). We derive an algorithm for this problem using relational algebra, a show how it may be implemented in Prolog. The motivation for the problem derives from a declarative framework for specifying compiler optimisations.

Original languageEnglish (US)
Pages (from-to)15-35
Number of pages21
JournalHigher-Order and Symbolic Computation
Issue number1-2
StatePublished - Mar 2003

Bibliographical note

Funding Information:
Three anonymous referees suggested many improvements to the presentation of this paper. Oege de Moor would like to thank Annie Liu for many constructive criticisms on the work presented here; she especially helped to improve the presentation of the derivation. She also made us aware of the existence of XSB as an appropriate tool for this type of experiment. Shin-Cheng Mu and Richard Bird provided valuable comments on an early draft. We would like to thank Microsoft Research for its generous support of this research programme, as part of the Intentional Programming project.


  • Program analysis
  • Program transformation
  • Query languages
  • Regular algebra


Dive into the research topics of 'Universal regular path queries'. Together they form a unique fingerprint.

Cite this