School of Computing

Quotienting Share for Dependency Analysis

Andy King, Jan-Georg Smaus, and Pat Hill

In Doaitse Swierstra, editor, European Symposium on Programming, volume 1576 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, April 1999 (c) Springer-Verlag, see also http://www.springer.de/comp/lncs/index.html.

Abstract

Def, the domain of definite Boolean functions, expresses (sure) dependencies between the program variables of, say, a constraint program. Share, on the other hand, captures the (possible) variable sharing between the variables of a logic program. The connection between these domains has been explored in the domain comparison and decomposition literature. We develop this link further and show how the \meet\ (as well as the \join) of Def can be modelled with efficient (quadratic) operations on Share. Further, we show how by compressing and widening Share and by rescheduling \meet\ operations, we can construct a dependency analysis that is surprisingly fast and precise, and comes with time- and space- performance guarantees. Unlike some other approaches, our analysis can be coded straightforwardly in Prolog.

Download publication 256 kbytes (PostScript)

Bibtex Record

@inproceedings{683,
author = {Andy King and Jan-Georg Smaus and Pat Hill},
title = {{Quotienting Share for Dependency Analysis}},
month = {April},
year = {1999},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {(c) Springer-Verlag, see also http://www.springer.de/comp/lncs/index.html},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1999/683},
    booktitle = {European Symposium on Programming},
    editor = {Doaitse Swierstra},
    publisher = {Springer-Verlag},
    refereed = {yes},
    series = {Lecture Notes in Computer Science},
    volume = {1576},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014