Universal regular path queries

O De Moor; David Lacey; E Van Wyk

doi:10.1023/A:1023063919574

Back

Journal article

Peer reviewed

Universal regular path queries

O De Moor, David Lacey and E Van Wyk

Higher-Order and Symbolic Computation, Vol.16(1), pp.15-35

2003

DOI: https://doi.org/10.1023/A:1023063919574

Files and links (1)

url

https://doi.org/10.1023/A:1023063919574View

Published Version

Abstract

program transformation

regular algebra

program analysis

query languages

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.

Details

Title: Universal regular path queries
Authors: O De Moor (Author) - University of Copenhagen, Denmark
David Lacey (Author) - University of Warwick, United Kingdom
E Van Wyk (Author) - University of Minnesota, United States
Publication details: Higher-Order and Symbolic Computation, Vol.16(1), pp.15-35
Publisher: Springer New York LLC
Date published: 2003
DOI: 10.1023/A:1023063919574
ISSN: 1388-3690
Organisation Unit: Cyber Institute; University of the Sunshine Coast, Queensland
Language: English
Record Identifier: 99449372402621
Output Type: Journal article

Metrics

362 Record Views