University of Minnesota
Software Engineering Center
/

You are here

Universal Regular Path Queries

Date of Publication: 
March 2003
Associated Research Groups: 
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 phi (of symbols for variables), together with all nodes n such that all paths n0 to n are in phi(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.
Venue: 
Higher Order and Symbolic Computation (HOSC) 16 (1-2): 15-35. A special issue dedicated to Bob Paige.
bibtex: 
@article{deMoor03, author = "de Moor, O. and Lacey, D. and Van Wyk, E.", title = "Universal Regular Path Queries", journal = "Higher Order and Symbolic Computation", volume = 16, number = "1-2", pages = "15--35", editor = "Olivier Danvy", year = 2003, note = "Special issue dedicated to Robert Paige" }