Universal Regular Path Queries

摘要

Given are a directed edge-labelled graph G with a distinguished node n_0, 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 n_0 → n are in φ(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.