|Publication Type||Conference Paper|
|Year of Publication||1999|
|Authors||King A, Smaus J-G, Hill PM|
|Editor||S. Swierstra D|
|Conference Name||Proceedings of the European Symposium on Programming|
|Keywords||abstract interpretation, groundness analysis, logic programming, mode analysis, quotient, sharing analysis, software verification, static 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.