Sharing and groundness dependencies in logic programs

Abstract

We investigate Jacobs and Langen's Sharing domain, introduced for the analysis of variable sharing in logic programs, and show that it is isomorphic to Marriott and Søndergaard's 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 analysi..