Algebraic Systems of Fixpoint Equations over Semirings: Theory and Applications

Algebraic systems of fixpoint equations $X = F(X)$ arise in various areas of computer science. In this thesis we study algorithms for solving algebraic systems based on Newton's method as proposed by (Esparza, Kiefer, Luttenberger, 2010). We first investigate the theoretical properties and algorithmics of Newton's method on semirings. Then we present FPsolve, an efficient and generic implementation of various methods for solving algebraic systems over semirings. Finally, we explore applications in database theory, formal languages, and natural language processing.
Algebraische Systeme von Fixpunktgleichungen finden Anwendung in verschiedenen Bereichen der Informatik. In dieser Arbeit beschäftigen wir uns mit Algorithmen zur Lösung von algebraischen Systemen, welche auf dem Newtonverfahren basieren (nach Espraza/Kiefer/Luttenberger, 2010). Wir untersuchen die theoretischen und algorithmischen Eigenschaften des Newtonverfahrens auf Semiringen. Anschließend stellen wir FPsolve vor, eine effiziente und generische Implementierung verschiedener Methoden zur Lösung algebraischer Systeme. Abschließend erkunden wir diverse Anwendungen.