Convergence of Newton's Method over Commutative Semirings

详细信息    查看全文

• 作者：Michael Luttenberger ; ^{luttenbe@model.in.tum.de" class="auth_mail" title="E-mail the corresponding author} ; Maximilian Schlund ; ^{schlund@model.in.tum.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Newton's method ; Polynomial fixed-point equations ; Semirings ; Algebraic language theory ; Horton&ndash ; Strahler number
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：246
• 期：Complete
• 页码：43-61
• 全文大小：546 K

文摘

We give a lower bound on the speed at which Newton's method (as defined in [11]) converges over arbitrary ω  -continuous commutative semirings. From this result, we deduce that Newton's method converges within a finite number of iterations over any semiring which is “collapsed at some k∈N$k\in \mathbb{N}$” (i.e. k=k+1$k=k+1$ holds) in the sense of Bloom and Ésik [2]. We apply these results to (1) obtain a generalization of Parikh's theorem, (2) compute the provenance of Datalog queries, and (3) analyze weighted pushdown systems. We further show how to compute Newton's method over any ω-continuous semiring by constructing a grammar unfolding w.r.t. “tree dimension”. We review several concepts equivalent to tree dimension and prove a new relation to pathwidth.