Sharing and Groundness Dependencies in Logic Programs

Michael Codish, Harald Søndergaard and Peter Stuckey

ACM Transactions on Programming Languages and Systems; 21 (5): 948-976, 1999

Abstract:

We investigate Jacobs and Langens Sharing domain, introduced for the analysis of variable sharing in logic programs, and show that it is isomorphic to Marriott and Sondergaards Pos domain, introduced for the analysis of groundness dependencies. Our key idea is to view the sets of variables in a Sharing domain element as the models of a corresponding Boolean function. This leads to a recasting of sharing analysis in terms of the property of ``not being affected by the binding of a single variable.' Such an ``unaffectedness dependency' analysis has close connections with groundness dependency analysis using positive Boolean functions. This new view improves our understanding of sharing analysis, and leads to an elegant expression of its combination with groundness dependency analysis based on the reduced product of Sharing and Pos. It also opens up new avenues for the efficient implementation of sharing analysis, for example using reduced order binary decision diagrams, as well as efficient implementation of the reduced product, using domain factorizations.

Available: bibtex entry compressed postscript

Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il