Beyond the elementary representations of program invariants over algebraic data types
Beyond the elementary representations of program invariants over algebraic data types
复制标题
超越代数数据类型上的程序不变量的基本表示
DOI：
10.1145/3453483.3454055
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Grigory Fedyukovich
中科院分区：
文献类型：
--
作者：
Y. Kostyukov;D. Mordvinov;Grigory Fedyukovich
一阶逻辑是表达计算属性的一种自然方式。它传统上用于各种程序逻辑中，用于表示正确性属性和证书。虽然这样的表示是表达一些理论，他们无法表达代数数据类型（ADT）的许多有趣的属性。在本文中，我们探讨了三种不同的方法来表示ADT操作程序的程序不变量：树自动机，和一阶公式有或没有大小限制。我们比较这些表示的表达能力，并证明了负的可定义性的一阶表示使用泵引理。我们提出了一种方法来自动推断ADT操作程序的程序不变量减少到一个有限的模型发现者。被称为RInGen的实现已被评估对国家的最先进的不变合成器，并已被实验证明是有竞争力的。特别是，由自动机表示的程序不变量能够表达更复杂的计算属性，并且它们的自动构造通常成本较低。
First-order logic is a natural way of expressing properties of computation. It is traditionally used in various program logics for expressing the correctness properties and certificates. Although such representations are expressive for some theories, they fail to express many interesting properties of algebraic data types (ADTs). In this paper, we explore three different approaches to represent program invariants of ADT-manipulating programs: tree automata, and first-order formulas with or without size constraints. We compare the expressive power of these representations and prove the negative definability of both first-order representations using the pumping lemmas. We present an approach to automatically infer program invariants of ADT-manipulating programs by a reduction to a finite model finder. The implementation called RInGen has been evaluated against state-of-the-art invariant synthesizers and has been experimentally shown to be competitive. In particular, program invariants represented by automata are capable of expressing more complex properties of computation and their automatic construction is often less expensive.
解决存在量化的喇叭子句
DOI：
10.1007/978-3-642-39799-8_61
发表时间：
2013
期刊：
影响因子：
--
作者：
Tewodros A. Beyene;Corneliu Popeea;Andrey Rybalchenko
通讯作者：
Andrey Rybalchenko