Geometric Quantifier Elimination Heuristics for Automatically Generating 
Octagonal and Max-plus Invariants

Kapur, Deepak; Zhang, Zhihai; Horbach, Matthias; Zhao, Hantao; Lu, Qi; Nguyen, ThanhVu

doi:10.1007/978-3-642-36675-8_11

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Book Chapter

Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants

MPS-Authors

There are no MPG-Authors in the publication available

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Kapur, D., Zhang, Z., Horbach, M., Zhao, H., Lu, Q., & Nguyen, T. (2013). Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants. In M. P. Bonacina, & M. E. Stickel (Eds.), Automated Reasoning and Mathematics (pp. 189-228). Berlin: Springer. doi:10.1007/978-3-642-36675-8_11.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-8385-C

Abstract

Geometric heuristics for the quantifier elimination approach presented by Kapur (2004) are investigated to automatically derive loop invariants expressing weakly relational numerical properties (such as l ≤ x ≤ h or l ≤ \pm x \pm y ≤q h) for imperative programs. Such properties have been successfully used to analyze commercial software consisting of hundreds of thousands of lines of code (using for example, the Astrée tool based on abstract interpretation framework proposed by Cousot and his group). The main attraction of the proposed approach is its much lower complexity in contrast to the abstract interpretation approach (O(n^2) in contrast to O(n^4), where n is the number of variables) with the ability to still generate invariants of comparable strength. This approach has been generalized to consider disjunctive invariants of the similar form, expressed using maximum function (such as \max(x+a,y+b,z+c,d) ≤ \max(x+e,y+f,z+g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well.