TY - JOUR

T1 - Convergence of Newton's Method over Commutative Semirings

AU - Luttenberger, Michael

AU - Schlund, Maximilian

N1 - Publisher Copyright:
© 2015 Elsevier Inc. All rights reserved.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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" (i.e. 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.

AB - 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" (i.e. 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.

KW - Algebraic language theory

KW - Horton-Strahler number

KW - Newton's method

KW - Polynomial fixed-point equations

KW - Semirings

UR - http://www.scopus.com/inward/record.url?scp=84949256477&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2015.11.008

DO - 10.1016/j.ic.2015.11.008

M3 - Article

AN - SCOPUS:84949256477

SN - 0890-5401

VL - 246

SP - 43

EP - 61

JO - Information and Computation

JF - Information and Computation

ER -