User: Guest  Login
Original title:
Solving Polynomial Systems on Semirings 
Original subtitle:
A Generalization of Newton's Method 
Translated title:
Lösen polynomieller Systeme über Semiringen 
Translated subtitle:
Eine Verallgemeinerung des Newton-Verfahrens 
Year:
2010 
Document type:
Dissertation 
Institution:
Fakultät für Informatik 
Advisor:
Esparza Estaun, Francisco Javier (Prof. Dr.) 
Referee:
Diekert, Volker (Prof. Dr.) 
Language:
en 
Subject group:
DAT Datenverarbeitung, Informatik 
Abstract:
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 fixe...    »
 
Translated abstract:
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...    »
 
Oral examination:
12.02.2010 
Pages:
190 
Last change:
10.03.2010