Polynomielle Systeme über Semiringen: Grundlagen, Algorithmen, Anwendungen

Polynomielle Gleichungssystem eüber Semiringen(PSES)sind Gleichungssystem der form X=f(X)，wobees sich be X bzw.f um einen Vektor von Variablen bzw.von Polynomenüber einem Semering Handelt.在基本原理问题中，L的存在是一种有效的逼近方法。程序分析和概率分析系统。在牛顿-费尔法伦的基础上，我们建立了一个统一的、标准的、非标准从牛顿-Verfahrens到Verfahrens的Weterhin haben wir Untere Schranken für die Konvergenzgeschwindigkeit des ton-Verfahrens im Spezialfall von psesüber den Nichtnsin甚至reellen zahlen gewinnen könnnen。麻省理工学院的设计项目并不能解决所有软件中的问题，因为它是一种新的技术。从牛顿-Verfahrens的世界范围内，我们可以看到，牛顿-Verfahrens-Verfahrens的世界范围内，牛顿-Verfahrens的技术规范是什么，这是因为牛顿-Verfahrens不是真正意义上的世界牛顿-Verfahrens的中心，而是世界上最重要的地方。我的算法是通过数据和有效的算法实现的牛顿-Verfahrens Benötigt。给出了程序分析、模型检验和计算机-代数-程序集成的算法。

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.