Widening Positive Boolean functions for Goal-dependent Groundness Analysis

Codish, M. and Heaton, A. and King, A. and Abo-Zaed, M. and Hill, P.M. (1998) Widening Positive Boolean functions for Goal-dependent Groundness Analysis. Technical report. University of Kent

Postscript
Download (183Kb)	Preview
PDF
Download (212Kb)	Preview

Abstract

The domain of positive Boolean functions, Pos, is by now well established for the analysis of the variable dependencies that arise within logic programs. Analyses based on Pos that use binary decision diagrams have been shown to be efficient for a wide range of practical programs. However, independent of the representation, assuming that P neq NP, an (unwidened) Pos analysis can never come with any efficiency guarantees because of its potentially explosive behaviour. This paper proposes a simple widening for (goal-dependent) groundness analysis of logic programs that guarantees scalability and efficiency. Experimental results indicate that the widening induces only a very small loss of precision.

Item Type:	Monograph (Technical report)
Uncontrolled keywords:	abstract interpretation, logic programming
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions:	Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User:	Mark Wheadon
Date Deposited:	22 Aug 2009 12:25
Last Modified:	25 Jun 2012 10:15
Resource URI:	http://kar.kent.ac.uk/id/eprint/21659 (The current URI for this page, for reference purposes)

• Depositors only (login required):