Skip to main content

Implementing Groundness Analysis with Definite Boolean Functions: 9th European Symposium on Programming, ESOP 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 Berlin, Germany, March 25 – April 2, 2000 Proceedings

Howe, Jacob M. and King, Andy (2000) Implementing Groundness Analysis with Definite Boolean Functions: 9th European Symposium on Programming, ESOP 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 Berlin, Germany, March 25 – April 2, 2000 Proceedings. In: Smolka, Gert, ed. European Symposium on Programming. Lecture Notes in Computer Science, 1782 . Springer, pp. 200-214. ISBN 978-3-540-67262-3. (doi:10.1007/3-540-46425-5_13)

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.

Item Type: Book section
DOI/Identification number: 10.1007/3-540-46425-5_13
Subjects: A General Works
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Andy King
Date Deposited: 13 Dec 2013 14:55 UTC
Last Modified: 29 May 2019 11:41 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37620 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year