First-order logic is a natural way of expressing the properties of computation, traditionally used in various program logics for expressing the correctness properties and certificates. Subsequently, modern methods in the automated inference of program invariants progress towards the construction of first-order definable invariants. 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 of representing the inductive invariants of ADT-manipulating programs: by first-order formulas, by tree automata and by first-order formulas with size constraints. We compare the expressive power of these representations. For this purposes, we formulate and prove the analogues of pumping lemmas for the elementary languages and use them to prove the negative definability results. We show how to automatically infer regular invariants of ADT-manipulating programs using finite model finders. We have implemented our approach and evaluated it against the state-of-art engines for the invariant inference in first-order logic for ADT-manipulating programs. Our evaluation shows that automata-based representation of invariants is more practical than the one based on first-order logic since invariants are capable of expressing more complex properties of the computation and their automatic construction is less expensive.


翻译:一级逻辑是表达计算特性的一种自然方式, 传统上在表达正确性属性和证书的各种程序逻辑中使用了这种逻辑。 随后, 程序变数的自动推断方法在构建第一级可定义变数的进展中采用了现代方法。 虽然这种表达方式对某些理论来说是表达的, 但是它们未能表达代数数据类型( ADTs) 的许多有趣的特性。 在本文中, 我们探索了三种代表ADT- 调控程序诱导变量的不同方法: 一阶公式、 树自上而下和 带有尺寸限制的一阶公式。 我们比较了这些表达方式的表达力。 为此, 我们制定并验证了用于初级语言的抽动 Lemmas 的模拟, 并用它们来证明负的可定义性结果。 我们展示了如何用有限的模型发现器自动推断出ADT- 调控程序( ADT- M) 的惯性。 我们运用了我们的方法, 并对照基于第一阶调调的公式、 直径可变数性逻辑的模型模型, 而不是基于一种更不易变式的逻辑的自动分析程序。 我们的评估显示的是, 一种更基于更难的逻辑的逻辑结构的逻辑结构的计算方法是更基于一种更难的逻辑结构。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
专知会员服务
52+阅读 · 2020年9月7日
【课程】纽约大学 DS-GA 1003 Machine Learning
专知会员服务
45+阅读 · 2019年10月29日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年6月4日
Arxiv
0+阅读 · 2021年6月2日
Arxiv
0+阅读 · 2021年6月1日
GeomCA: Geometric Evaluation of Data Representations
Arxiv
11+阅读 · 2021年5月26日
Arxiv
14+阅读 · 2020年12月17日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员