Sharing and groundness dependencies in logic programs

We investigate Jacobs and Langen's Sharing domain, introduced for the analy sis of variable sharing in logic programs, and show that it is isomorphic t o Marriott and Sondergaard's Pos domain, introduced for the analysis of gro undness dependencies. Our key idea is to view the sets of variables in a Sh aring domain element as the models of a corresponding Boolean function. Thi s 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 "unaffectedne ss dependency" analysis has close connections with groundness dependency an alysis using positive Boolean functions. This new view improves our underst anding of sharing analysis, and leads to an elegant expression of its combi nation with groundness dependency analysis based on the reduced product of Sharing and Pos. It also opens up new avenues for the efficient implementat ion of sharing analysis, for example using reduced order binary decision di agrams, as well as efficient implementation of the reduced product, using d omain factorizations.