【24h】

Abstraction Refinement of Linear Programs with Arrays

机译:数组线性程序的抽象优化

获取原文
获取原文并翻译 | 示例

摘要

In previous work we presented a model checking procedure for linear programs, i.e. programs in which variables range over a numeric domain and expressions involve linear combinations of the variables. In this paper we lift our model checking procedure for linear programs to deal with arrays via iterative abstraction refinement. While most approaches are based on predicate abstraction and therefore the abstraction is relative to sets of predicates, in our approach the abstraction is relative to sets of variables and array indexes, and the abstract program can express complex correlations between program variables and array elements. Thus, while arrays are problematic for most of the approaches based on predicate abstraction, our approach treats them in a precise way. This is an important feature as arrays are ubiquitous in programming. We provide a detailed account of both the abstraction and the refinement processes, discuss their implementation in the EUREKA tool, and present experimental results that confirm the effectiveness of our approach on a number of programs of interest.
机译:在以前的工作中,我们提出了一种用于线性程序的模型检查程序,即其中变量在数值域内变化且表达式包含变量线性组合的程序。在本文中,我们提出了用于线性程序的模型检查程序,以通过迭代抽象提炼来处理数组。尽管大多数方法都基于谓词抽象,因此抽象是相对于谓词集的,但在我们的方法中,抽象是相对于变量和数组索引的集,而抽象程序可以表达程序变量和数组元素之间的复杂关联。因此,虽然数组对于大多数基于谓词抽象的方法来说都是成问题的,但我们的方法以精确的方式对待它们。这是一项重要功能,因为数组在编程中无处不在。我们提供了抽象和优化过程的详细说明,讨论了它们在EUREKA工具中的实现,并提供了实验结果,这些结果证实了我们的方法在许多感兴趣的程序上的有效性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号