On Fixed Point Equations over Commutative Semirings
On Fixed Point Equations over Commutative Semirings
复制标题
关于交换半环上的不动点方程
DOI：
10.1007/978-3-540-70918-3_26
复制
发表时间：
2007
影响因子：
--
通讯作者：
Michael Luttenberger
中科院分区：
文献类型：
--
作者：
J. Esparza;S. Kiefer;Michael Luttenberger
固定点= f（x）上的ω-连续时间可以看作是序列分析的数学基础。 。和Kozen [5]是任意交换ω连续半段的一般算法的实例，我们在第二个贡献中提高了[5]的O（3n）结合，并表明其加速度在迭代后达到µF方程数的数量。
Fixed point equations x = f (x) over ω-continuous semirings can be seen as the mathematical foundation of interprocedural program analysis. The sequence 0, f (0), f2(0), . . . converges to the least fixed point µf . The convergence can be accelerated if the underlying semiring is commutative. We show that accelerations in the literature, namely Newton's method for the arithmetic semiring [4] and an acceleration for commutative Kleene algebras due to Hopkins and Kozen [5], are instances of a general algorithm for arbitrary commutative ω-continuous semirings. In a second contribution, we improve the O(3n) bound of [5] and show that their acceleration reaches µf after n iterations, where n is the number of equations. Finally, we apply the Hopkins-Kozen acceleration to itself and study the resulting hierarchy of increasingly fast accelerations.