An Introduction to Newton’s Method on Semirings

Javier Esparza (Technische Universität München)
Logic and Algebra for Query Evaluation

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.