We study the calculation of the least fixed point of systems of polynomials on semirings. These systems arise in several branches of computer science, e.g. in the analysis of procedural programs. Our main result is the generalization of Newton's method to this more general setting. We show that on semirings Newton's method converges at least as fast as the standard fixed point iteration. Further, we identify classes of semirings on which Newton's method reaches the least fixed point after a finite number of steps in contrast to the standard fixed point iteration.     «

We study the calculation of the least fixed point of systems of polynomials on semirings. These systems arise in several branches of computer science, e.g. in the analysis of procedural programs. Our main result is the generalization of Newton's method to this more general setting. We show that on semirings Newton's method converges at least as fast as the standard fixed point iteration. Further, we identify classes of semirings on which Newton's method reaches the least fixed point...     »

Es wird die Berechnung des kleinsten Fixpunkts polynomieller Systeme über Semiringen betrachtet. Diese Systeme ergeben sich innerhalb verschiedener Bereiche der Informatik, z.B. bei der Analyse von prozeduralen Programmen. Das Hauptergebnis ist die Verallgemeinerung des Newton-Verfahrens. Es wird gezeigt, dass das Newton-Verfahren über Semiringen stets mindestens so schnell wie die Standardfixpunktiteration konvergiert. Weiterhin werden Klassen von Semiringen ermittelt, über denen das Newton-Verfahren den kleinsten Fixpunkt innerhalb endlich vieler Schritt erreicht im Gegensatz zur Standardfixpunktiteration.     «

Es wird die Berechnung des kleinsten Fixpunkts polynomieller Systeme über Semiringen betrachtet. Diese Systeme ergeben sich innerhalb verschiedener Bereiche der Informatik, z.B. bei der Analyse von prozeduralen Programmen. Das Hauptergebnis ist die Verallgemeinerung des Newton-Verfahrens. Es wird gezeigt, dass das Newton-Verfahren über Semiringen stets mindestens so schnell wie die Standardfixpunktiteration konvergiert. Weiterhin werden Klassen von Semiringen ermittelt, über denen das Newto...     »