We consider the problem of deciding termination of single-path while loops with integer variables, affine updates, and affine guard conditions. The question is whether such a loop terminates on all integer initial values. This problem is known to be decidable for the subclass of loops whose update matrices are diagonalisable, but the general case has remained open since being conjectured decidable by Tiwari in 2004. In this paper we show decidability of determining termination for arbitrary update matrices, confirming Tiwari's conjecture. For the class of loops considered in this paper, the question of deciding termination on a specific initial value is a longstanding open problem in number theory. The key to our decision procedure is in showing how to circumvent the difficulties inherent in deciding termination on a fixed initial value.


翻译:我们考虑了在以整数变量、折叠式更新和折叠式保护条件环绕时决定终止单一路径的问题。 问题在于这种环绕是否在所有整数初始值上都终止。 这个问题对于更新矩阵可以对等化的环绕子类来说是可分解的, 但一般情况自2004年提瓦里预测可分解以来一直没有解决。 本文显示,确定任意更新矩阵终止的可变性, 证实了蒂瓦里的猜想。 对于本文所考虑的环绕类别, 决定特定初始值终止的问题在数字理论上是一个长期的开放问题。 我们决定程序的关键在于显示如何避免在确定固定初始值终止时所固有的困难。

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
专知会员服务
61+阅读 · 2020年3月4日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年1月25日
Arxiv
0+阅读 · 2022年1月25日
Arxiv
0+阅读 · 2022年1月23日
Arxiv
0+阅读 · 2022年1月21日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
计算机类 | 国际会议信息7条
Call4Papers
3+阅读 · 2017年11月17日
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员