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 φ (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 language | English (US) |
|---|---|
| Pages (from-to) | 15-35 |
| Number of pages | 21 |
| Journal | Higher-Order and Symbolic Computation |
| Volume | 16 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - 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.
Keywords
- Program analysis
- Program transformation
- Query languages
- Regular algebra