𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Worst-case groundness analysis using positive Boolean functions

✍ Scribed by Michael Codish

Book ID
104344538
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
61 KB
Volume
41
Category
Article
ISSN
0743-1066

No coin nor oath required. For personal study only.

✦ Synopsis

This note illustrates a theoretical worst-case scenario for groundness analyses obtained through abstract interpretation over the abstract domain of positive Boolean functions. A sequence of programs is given for which any Pos-based abstract interpretation for groundness analysis follows an exponential chain. Another sequence of programs is given for which a state-of-the-art implementation based on ROBDDs gives a result of exponential size in only three iterations. The moral of the story is that a serious Pos analyser must incorporate some form of widening to protect itself from the inherent complexity of the underlying domain.

πŸ“œ SIMILAR VOLUMES

Worst case analysis of resistive network
Worst case analysis of resistive networks using linear programming approach
✍ Mona Elwakkad Zaghloul πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 682 KB

It is shown thatfor DC networks in which certain components are allowed to vary, the worst case DC problem can be solved by solving a linear programming problem. The constraints used in the linear programming problem are determinedfrom the elements tolerance regions. This enables us to obtain the wo