School of Computing

Widening Positive Boolean functions for Goal-dependent Groundness Analysis

Michael Codish, Andy Heaton, Andy King, Muhamed Abo-Zaed, and Pat Hill

Technical Report 12-98, Computing Laboratory, May 1998.

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.

Download publication 183 kbytes (PostScript)

Bibtex Record

@techreport{589,
author = {Michael Codish and Andy Heaton and Andy King and Muhamed Abo-Zaed and Pat Hill},
title = {Widening {P}ositive {B}oolean functions for {G}oal-dependent {G}roundness {A}nalysis},
month = {May},
year = {1998},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1998/589},
    institution = {Computing Laboratory},
    number = {12-98},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014