




Publications  On Fixed Point Equations over Commutative Semirings





Reference:
Javier Esparza, Stefan Kiefer, and Michael Luttenberger. On fixed point equations over commutative semirings. In Wolfgang Thomas and Pascal Weil, editors, Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 4393 of LNCS, pages 296–307, Aachen, Germany, 2007. Springer.
Abstract:
Fixed point equations x = f(x) over omegacontinuous semirings can be seen as the mathematical foundation of interprocedural program analysis. The sequence 0, f(0), f(f(0)), ... converges to the least fixed point mu.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 and an acceleration for commutative Kleene algebras due to Hopkins and Kozen, are instances of a general algorithm for arbitrary commutative omegacontinuous semirings. In a second contribution, we improve the O(3^n) bound of Hopkins and Kozen and show that their acceleration reaches mu.f after n iterations, where n is the number of equations. Finally, we apply the HopkinsKozen acceleration to itself and study the resulting hierarchy of increasingly fast accelerations.
Suggested BibTeX entry:
@inproceedings{EKL07,
address = {Aachen, Germany},
author = {Javier Esparza and Stefan Kiefer and Michael Luttenberger},
booktitle = {Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS)},
editor = {Wolfgang Thomas and Pascal Weil},
pages = {296307},
publisher = {Springer},
series = {LNCS},
title = {On Fixed Point Equations over Commutative Semirings},
volume = {4393},
year = {2007}
}




