© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Implementing Groundness Analysis with Definite Boolean Functions
J. M. Howe and A. King
In G. Smolka, editor, European Symposium on Programming, volume 1782 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, March 2000 Copyright Springer-Verlag, see http://www.springer.de./comp/lncs/index.html.Abstract
The domain of definite Boolean functions, $\mydef$, can be used to express the groundness of, and trace grounding dependencies between, program variables in (constraint) logic programs. In this paper, previously unexploited computational properties of $\mydef$ are utilised to develop an efficient and succinct groundness analyser that can be coded in Prolog. In particular, entailment checking is used to prevent unnecessary least upper bound calculations. It is also demonstrated that join can be defined in terms of other operations, thereby eliminating code and removing the need for preprocessing formulae to a normal form. This saves space and time. Furthermore, the join can be adapted to straightforwardly implement the downward closure operator that arises in set sharing analyses. Experimental results indicate that the new $\mydef$ implementation gives favourable results in comparison with BDD-based groundness analyses.
Download publication 92 kbytesBibtex Record
@inproceedings{949,
author = {Howe, J. M. and King, A.},
title = {Implementing {G}roundness {A}nalysis with {D}efinite {B}oolean {F}unctions},
month = {March},
year = {2000},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {Copyright Springer-Verlag, see http://www.springer.de./comp/lncs/index.html},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2000/949},
booktitle = {European Symposium on Programming},
editor = {Smolka, G.},
publication_type = {inproceedings},
publisher = {Springer-Verlag},
series = {Lecture Notes in Computer Science},
submission_id = {22118_945700074},
volume = {1782},
}