Termination of linear loops under commutative updates
Termination of linear loops under commutative updates
复制标题
交换更新下线性循环的终止
DOI：
10.1145/3597066.3597101
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Dong R
中科院分区：
文献类型：
--
作者：
Dong R
考虑如下问题：给定d × d有理矩阵A1，…，Ak和一个多面体锥，判定是否存在一个非零向量，其与A1，…，Ak相乘的轨道包含在.这个问题可以被解释为验证多路径while循环的终止与线性更新和线性保护条件。我们证明了这个问题是可判定的交换可逆矩阵A1，...，Ak。我们决策过程的关键是用纯代数的方式重新解释这个问题。也就是说，我们发现了它与多项式环上的模以及多项式半环上的模的联系。循环终止的问题，然后减少到决定是否包含一个“积极”的元素的子模块。
We consider the following problem: given d × d rational matrices A1, …, Ak and a polyhedral cone , decide whether there exists a non-zero vector whose orbit under multiplication by A1, …, Ak is contained in . This problem can be interpreted as verifying the termination of multi-path while loops with linear updates and linear guard conditions. We show that this problem is decidable for commuting invertible matrices A1, …, Ak. The key to our decision procedure is to reinterpret this problem in a purely algebraic manner. Namely, we discover its connection with modules over the polynomial ring as well as the polynomial semiring . The loop termination problem is then reduced to deciding whether a submodule of contains a “positive” element.
登录
查看更多内容
数值循环的闭合形式
影响因子：
--
作者：
Zachary Kincaid;J. Breck;John Cyphert;T. Reps
通讯作者：
T. Reps
DOI：
10.1145/3209108.3209142
发表时间：
2018-02
期刊：
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
E. Hrushovski;Joël Ouaknine;Amaury Pouly;J. Worrell
通讯作者：
E. Hrushovski;Joël Ouaknine;Amaury Pouly;J. Worrell
DOI：
10.1137/1.9781611973402.27
发表时间：
2013-07
期刊：
ArXiv
影响因子：
--
作者：
Joël Ouaknine;J. Worrell
通讯作者：
Joël Ouaknine;J. Worrell
DOI：
--
发表时间：
1996
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
L. Babai;R. Beals;Jin;G. Ivanyos;E. Luks
通讯作者：
E. Luks
影响因子：
2.5
作者：
Joël Ouaknine;Amaury Pouly;João Sousa;J. Worrell
通讯作者：
J. Worrell