TY - GEN
T1 - Newton's method for ω-continuous semirings
AU - Esparza, Javier
AU - Kiefer, Stefan
AU - Luttenberger, Michael
N1 - Funding Information:
This work was in part supported by the DFG project Algorithms for Software Model Checking.
PY - 2008
Y1 - 2008
N2 - Fixed point equations over X = f(X) ω-continuous semirings are a natural mathematical foundation of interprocedural program analysis. Generic algorithms for solving these equations are based on Kleene's theorem, which states that the sequence 0, f(0), f(f(0)),... converges to the least fixed point. However, this approach is often inefficient. We report on recent work in which we extend Newton's method, the well-known technique from numerical mathematics, to arbitrary ω-continuous semirings, and analyze its convergence speed in the real semiring.
AB - Fixed point equations over X = f(X) ω-continuous semirings are a natural mathematical foundation of interprocedural program analysis. Generic algorithms for solving these equations are based on Kleene's theorem, which states that the sequence 0, f(0), f(f(0)),... converges to the least fixed point. However, this approach is often inefficient. We report on recent work in which we extend Newton's method, the well-known technique from numerical mathematics, to arbitrary ω-continuous semirings, and analyze its convergence speed in the real semiring.
UR - http://www.scopus.com/inward/record.url?scp=49049118477&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-70583-3_2
DO - 10.1007/978-3-540-70583-3_2
M3 - Conference contribution
AN - SCOPUS:49049118477
SN - 3540705821
SN - 9783540705826
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 14
EP - 26
BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Y2 - 7 July 2008 through 11 July 2008
ER -