Abstract
We survey work we conducted between 2007 and 2016 on solving systems of polynomial fixpoint equations over omega-continuous semirings. We show that a suitable generalization of Newton's method, the well-known technique from numerical analysis, can be generalized to this setting. We characterize the information contained in the Newton approximants to the fixpoint, and describe some applications.
- Javier Esparza, Stefan Kiefer, Michael Luttenberger: Newton's Method for omega-Continuous Semirings. ICALP (2) 2008: 14-26. https://link.springer.com/chapter/10.1007/978-3-540-70583-3_2
- J Esparza, S Kiefer, M Luttenberger: Newtonian program analysis. Journal of the ACM (JACM), 2010. https://dl.acm.org/doi/abs/10.1145/1857914.1857917
- Javier Esparza, Stefan Kiefer, Michael Luttenberger: Derivation tree analysis for accelerated fixed-point computation. Theor. Comput. Sci. 412(28): 3226-3241 (2011). https://doi.org/10.1016/j.tcs.2011.03.020