Reflections on Termination of Linear Loops
Reflections on Termination of Linear Loops
复制标题
对线性循环终止的思考
DOI：
10.1007/978-3-030-81688-9_3
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kincaid, Zachary
中科院分区：
文献类型：
--
作者：
Zhu, Shaowei;Kincaid, Zachary
本文展示了如何线性动力系统的技术可以用来推理一般循环的行为。我们提出了两个主要结果。首先，我们证明了每一个可以用线性整数运算中的转移公式表示的回路都有一个最优模型作为一个确定的仿射转移系统。其次，我们证明了对于任何具有整数特征值的线性动力系统f和任何整数算术公式G，存在一个线性整数算术公式，该公式对G最终不变的状态f完全成立。结合这两个，我们开发了一个单调的条件终止分析一般循环。
This paper shows how techniques for linear dynamical systems can be used to reason about the behavior of general loops. We present two main results. First, we show that every loop that can be expressed as a transition formula in linear integer arithmetic has abestmodel as adeterministic affine transition system. Second, we show that for any linear dynamical systemfwith integer eigenvalues and any integer arithmetic formulaG, there is a linear integer arithmetic formula that holds exactly for the states offfor whichGis eventually invariant. Combining the two, we develop a monotone conditional termination analysis for general loops.
登录
查看更多内容
DOI：
10.1007/978-3-030-45237-7_32
发表时间：
2020-03-13
期刊：
Tools and Algorithms for the Construction and Analysis of Systems
影响因子：
--
作者：
Dietsch D;Heizmann M;Nutz A;Schätzle C;Schüssele F
通讯作者：
Schüssele F
通过抽象机的数值不变量
DOI：
10.1007/978-3-319-99725-4_3
发表时间：
2018
期刊：
ArXiv
影响因子：
--
作者：
Zachary Kincaid
通讯作者：
Zachary Kincaid
数值循环的闭合形式
影响因子：
--
作者：
Zachary Kincaid;J. Breck;John Cyphert;T. Reps
通讯作者：
T. Reps
DOI：
10.1016/0024-3795(81)90106-3
发表时间：
2020-11
期刊：
--
影响因子：
--
作者：
Tzuong-Tsieng Moh
通讯作者：
Tzuong-Tsieng Moh
冲突驱动的有条件终止
DOI：
10.1007/978-3-319-21668-3_16
发表时间：
2015
期刊：
Tools and Algorithms for the Construction and Analysis of Systems
影响因子：
--
作者：
V. D'Silva;Caterina Urban
通讯作者：
Caterina Urban