کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426741 | 686254 | 2016 | 19 صفحه PDF | دانلود رایگان |
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∈Nk∈N” (i.e. k=k+1k=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.
Journal: Information and Computation - Volume 246, February 2016, Pages 43–61