Quotienting Share for Dependency Analysis

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.