Worst-case groundness analysis using definite Boolean functions
From MaRDI portal
Publication:4452643
DOI10.1017/S1471068401001077zbMATH Open1103.68460arXivcs/0405101OpenAlexW1998384504MaRDI QIDQ4452643FDOQ4452643
Authors: Samir Genaim, Michael Codish, Jacob M. Howe 
Publication date: 1 March 2004
Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/cs/0405101
Recommendations
Cited In (5)
This page was built for publication: Worst-case groundness analysis using definite Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4452643)
