TY - GEN
T1 - On fixed point equations over commutative semirings
AU - Esparza, Javier
AU - Kiefer, Stefan
AU - Luttenberger, Michael
PY - 2007
Y1 - 2007
N2 - 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 w-continuous semirings. In a second contribution, we improve the Ο(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.
AB - 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 w-continuous semirings. In a second contribution, we improve the Ο(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.
UR - http://www.scopus.com/inward/record.url?scp=34548081652&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-70918-3_26
DO - 10.1007/978-3-540-70918-3_26
M3 - Conference contribution
AN - SCOPUS:34548081652
SN - 9783540709176
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 296
EP - 307
BT - STACS 2007 - 24th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
PB - Springer Verlag
T2 - 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007
Y2 - 22 February 2007 through 24 February 2007
ER -