Worst-Case Groundness Analysis Using Definite Boolean Functions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
Appeared in Theory and Practice of Logic Programming, vol. 1, no. 5, 2001

Keywords

Programming Languages, D.1.6; D.3.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32169

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0405101
 http://arxiv.org/abs/cs/0405101
 Theory and Practice of Logic Programming, vol. 1, no. 5, 2001

Collections

arXiv