geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants
文献类型：期刊论文
| 作者 | Kapur Deepak ; Zhang Zhihai ; Horbach Matthias ; Zhao Hengjun ; Lu Qi ; Nguyen ThanhVu |
| 刊名 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 |
| 出版日期 | 2013 |
| 卷号 | 7788页码:189-228 |
| 关键词 | Abstracting |
| ISSN号 | 0302-9743 |
| 中文摘要 | 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 ±x ±y &le 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 Astre´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) &le max (x + e,y + f,z + g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well. © Springer-Verlag Berlin Heidelberg 2013. |
| 英文摘要 | 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 ±x ±y &le 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 Astre´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) &le max (x + e,y + f,z + g,h)), thus enabling automatic generation of a subclass of disjunctive invariants for imperative programs as well. © Springer-Verlag Berlin Heidelberg 2013. |
| 收录类别 | EI |
| 语种 | 英语 |
| 公开日期 | 2013-09-17 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/15627]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Kapur Deepak,Zhang Zhihai,Horbach Matthias,et al. geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants[J]. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2013,7788:189-228. |
| APA | Kapur Deepak,Zhang Zhihai,Horbach Matthias,Zhao Hengjun,Lu Qi,&Nguyen ThanhVu.(2013).geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants.Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),7788,189-228. |
| MLA | Kapur Deepak,et al."geometric quantifier elimination heuristics for automatically generating octagonal and max-plus invariants".Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7788(2013):189-228. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。