
The Definite Approach to Dependency AnalysisSamir Genaim and Michael Codish
Presented at the APPIAGULPPRODE 2000
Joint Conference on Declarative Programming (La Habana);
2000
Abstract:We propose a new representation for the domain of Definite Boolean functions. The key idea is to view the set of models of a Boolean function as an incidence relation between variables and models. This enables two dual representations: the usual one, in terms of models, specifying which variables they contain; and the other in terms of variables, specifying which models contain them. We adopt the dual representation which provides a clean theoretical basis for the definition of efficient operations on Def in terms of classic ACI1 unification theory. Our approach illustrates in an interesting way the relation of Def to the wellknown setSharing domain which can also be represented in terms of sets of models and ACI1 unification. From the practical side, a prototype implementation provides promising results which indicate that this representation supports efficient groundness analysis using Def formula.Available: bibtex entry compressed postscript Michael Codish The Department of Computer Science BenGurion University of the Negev PoB 653, BeerSheva, 84105, Israel mcodish@cs.bgu.ac.il
