TY - GEN
T1 - An extension of Newton's method to ω-continuous semirings
AU - Esparza, Javier
AU - Kiefer, Stefan
AU - Luttenberger, Michael
PY - 2007
Y1 - 2007
N2 - Fixed point equations x = F(x) over ω-continuous semi-rings are a natural mathematical foundation of interprocedural program analysis. Equations over the semiring of the real numbers can be solved numerically using Newton's method. We generalize the method to any ω-continuous semiring and show that it converges faster to the least fixed point than the Kleene sequence 0, F(O), F(F(O)),... We prove that the Newton approximants in the semiring of languages coincide with finiteindex approximations studied by several authors in the 1960s. Finally, we apply our results to the analysis of stochastic context-free grammars.
AB - Fixed point equations x = F(x) over ω-continuous semi-rings are a natural mathematical foundation of interprocedural program analysis. Equations over the semiring of the real numbers can be solved numerically using Newton's method. We generalize the method to any ω-continuous semiring and show that it converges faster to the least fixed point than the Kleene sequence 0, F(O), F(F(O)),... We prove that the Newton approximants in the semiring of languages coincide with finiteindex approximations studied by several authors in the 1960s. Finally, we apply our results to the analysis of stochastic context-free grammars.
UR - http://www.scopus.com/inward/record.url?scp=34548069749&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73208-2_17
DO - 10.1007/978-3-540-73208-2_17
M3 - Conference contribution
AN - SCOPUS:34548069749
SN - 3540732071
SN - 9783540732075
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 157
EP - 168
BT - Developments in Language Theory - 11th International Conference, DLT 2007 Proceedings
PB - Springer Verlag
T2 - 11th International Conference on Developments in Language Theory, DLT 2007
Y2 - 3 July 2007 through 6 July 2007
ER -