Part, Chapter of a Book
@InBook, Buchkapitel
Beitrag im Sammelband


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

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

dblp
dblp
dblp
dblp
dblp
dblp

Not MPG Author(s):

Kapur, Deepak
Zhang, Zhihai
Zhao, Hantao
Lu, Qi
Nguyen, ThanhVu

Editor(s):

Bonacina, Maria Paola
Stickel, Mark E.

dblp
dblp

Not MPII Editor(s):

Bonacina, Maria Paola
Stickel, Mark E.

BibTeX cite key*:

Horbach2013McCune

Title, Booktitle

Title*:

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

Booktitle*:

Automated Reasoning and Mathematics: Essays in Memory of William McCune

Chapter:


Series:

LNAI

Language:

English

Publisher

Name*:

Springer

URL:


Address*:

Berlin

Publication Type:


Vol, No, pp., Year

Volume:

7788

Number:


Edition:


Pages*:

189-228

Month:


VG Wort Pages:

68

ISBN:


Year*:

2014

Abstract, Links, ©

Note:


LaTeX 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 \le x \le h$ or $l \le \pm x \pm y \leq 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\'ee 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) \le \max(x+e,y+f,z+g,h)$), thus enabling automatic generation of a subclass of disjunctive
invariants for imperative programs as well.

URL Abstract:


Tags, Keywords:


Copyright Message:


HyperLinks / References / URLs:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Automation of Logic

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort
BibTeX Entry:
@INBOOK{Horbach2013McCune,
AUTHOR = {Kapur, Deepak and Zhang, Zhihai and Horbach, Matthias and Zhao, Hantao and Lu, Qi and Nguyen, ThanhVu},
EDITOR = {Bonacina, Maria Paola and Stickel, Mark E.},
TITLE = {Geometric Quantifier Elimination Heuristics for Automatically Generating Octagonal and Max-plus Invariants},
BOOKTITLE = {Automated Reasoning and Mathematics: Essays in Memory of William McCune},
PUBLISHER = {Springer},
YEAR = {2014},
VOLUME = {7788},
PAGES = {189--228},
SERIES = {LNAI},
ADDRESS = {Berlin},
}


Entry last modified by Matthias Horbach, 05/20/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/24/2014 12:38:00 PM
Revision
0.



Editor
Matthias Horbach



Edit Date
01/24/2014 12:38:00 PM