Implementing groundness analysis with definite Boolean functions

Howe, J.M. and King, A. (2000) Implementing groundness analysis with definite Boolean functions. Lecture Notes in Computer Science, 1782 . pp. 200-214. ISSN 0302-9743.

Other (zd)
Download (92Kb)
PDF
Download (239Kb)	Preview

Abstract

The domain of definite Boolean functions, Def, 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 Def 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 Def implementation gives favourable results in comparison with BDD-based groundness analyses.

Item Type:	Article
Additional information:	Conference Information: Joint European Conference on Theory and Practice of Software (ETAPS 2000) BERLIN, GERMANY, MAR 25-APR 02, 2000 Inst Communicat & Software Technol TU Berlin; European Assoc Program Languages & Syst; European Assoc Theoret Comp Sci; European Assoc Software Dev Sci
Uncontrolled keywords:	abstract interpretation; (constraint) logic programs; definite Boolean functions; groundness analysis
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Divisions:	Faculties > Science Technology and Medical Studies > School of Computing
Depositing User:	O.O. Odanye
Date Deposited:	14 May 2009 09:08
Last Modified:	25 Jun 2012 14:16
Resource URI:	http://kar.kent.ac.uk/id/eprint/16239 (The current URI for this page, for reference purposes)

• Depositors only (login required):