Polynomielle Systeme über Semiringen: Grundlagen, Algorithmen, Anwendungen

• Antragsteller: Professor Dr. Javier Esparza
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 192404487

Polynomielle Gleichungssysteme über Semiringen (PSEs) sind Gleichungssysteme der Form X = f(X), wobei es sich bei X bzw. f um einen Vektor von Variablen bzw. von Polynomen über einem Semiring handelt. Die effiziente Berechnung bzw. Approximation der kleinsten Lösung eines PSEs (soweit existent) ist ein fundamentales Problem u.a. im Bereich der formalen Sprachen, der Programmanalyse und der Analyse probabilistischer Systeme. In den vergangenen Jahren haben wir gezeigt, dass sich das Newton-Verfahren, ein Standardverfahren zur Approximation der Nullstellen nichtlinearer Funktionen über den reellen Zahlen, auf den Fall von PSEs über Semiringen verallgemeinern lässt. Weiterhin haben wir untere Schranken für die Konvergenzgeschwindigkeit des Newton-Verfahrens im Spezialfall von PSEs über den nichtnegativen reellen Zahlen gewinnen können. Mit diesem Projekt wollen wir unsere bisherigen Ergebnisse sowohl vertiefen als auch in Softwarewerkzeugen umsetzen: Im Bereich der Grundlagen stellt sich die Frage nach einem rein algebraischen Beweis für ein zentralen Konvergenzergebnisses bzgl. des verallgemeinerten Newton-Verfahrens; auch ist nur für einige spezielle Semiringe bekannt, dass sich das Newton-Verfahren dort vereinfachen lässt; schließlich ist eine zentrale Vermutung über die Konvergenzgeschwindigkeit des Newton-Verfahrens im Fall reeller PSEs noch unbeantwortet. Im Bereich der Algorithmik werden passende Datenstrukturen und effiziente Algorithmen für die Implementierung des verallgemeinerten Newton-Verfahrens benötigt. Auf Anwendungsseite sollen die Algorithmen in Programmanalysewerkzeuge, Model-Checker und Computer-Algebra-Programme integriert werden.

• DFG-Verfahren: Sachbeihilfen
• Beteiligte Person: Dr. Michael Luttenberger