© University of Kent - Contact | Feedback | Legal | FOI | Cookies
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}, }