Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-11T21:42:34.499Z Has data issue: false hasContentIssue false

Worst-case groundness analysis using definite Boolean functions

Published online by Cambridge University Press:  18 October 2001

SAMIR GENAIM
Affiliation:
Department of Computer Science, Ben-Gurion University of the Negev, PO Box 653, 84105 Israel (e-mail: mcodish@cs.bgu.ac.il)
MICHAEL CODISH
Affiliation:
Department of Computer Science, Ben-Gurion University of the Negev, PO Box 653, 84105 Israel (e-mail: mcodish@cs.bgu.ac.il)
JACOB M. HOWE
Affiliation:
Computing Laboratory, University of Kent, Canterbury, Kent, UK
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This note illustrates theoretical worst-case scenarios for groundness analyses obtained through abstract interpretation over the abstract domains of definite (Def) and positive (Pos) Boolean functions. For Def, an example is given for which any Def-based abstract interpretation for groundness analysis follows a chain which is exponential in the number of argument positions as well as in the number of clauses but sub-exponential in the size of the program. For Pos, we strengthen a previous result by illustrating an example for which any Pos-based abstract interpretation for groundness analysis follows a chain which is exponential in the size of the program. It remains an open problem to determine if the worst case for Def is really as bad as that for Pos.

Type
TECHNICAL NOTE
Copyright
© 2001 Cambridge University Press