Computer Science – Logic in Computer Science
Scientific paper
2011-11-22
Computer Science
Logic in Computer Science
32 pages, 9 figures, preliminary version appeared in ESOP (European Symposium On Programming) 2010; LMCS 8 (1:1) 2012
Scientific paper
10.2168/LMCS-8(1:01)2012
We introduce a new domain for finding precise numerical invariants of programs by abstract interpretation. This domain, which consists of level sets of non-linear functions, generalizes the domain of linear "templates" introduced by Manna, Sankaranarayanan, and Sipma. In the case of quadratic templates, we use Shor's semi-definite relaxation to derive computable yet precise abstractions of semantic functionals, and we show that the abstract fixpoint equation can be solved accurately by coupling policy iteration and semi-definite programming. We demonstrate the interest of our approach on a series of examples (filters, integration schemes) including a degenerate one (symplectic scheme).
Adjé Assalé
Gaubert Stephane
Goubault Eric
No associations
LandOfFree
Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coupling policy iteration with semi-definite relaxation to compute accurate numerical invariants in static analysis will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-553630