Textdokument
Lösen polynomieller Gleichungssysteme über Semiringen
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2011
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Diese Dissertation betracht Gleichungssysteme der Form X1 = f1(X1,...,Xn),...,Xn = fn(X1,...,Xn) (kurz: X = f(X)), wobei deren ,,rechte Seiten” fi durch multivariate Polynome über sogenannten w-stetigen Semiringen gegeben sind, und diskutierte Verfahren zur Approximation bzw. Bestimmung deren kleinster Lösung μf. Diese Gleichungssysteme treten in verschiedensten Bereichen der Informatik auf. Die bekanntesten Beispiele stellen die Datenflussanalyse (prozeduraler) Programme (in diesem Fall ist das Analyseergebnis durch μf gegeben) und die Theorie der formalen Sprachen (hier entspricht X = f(X) einer kontextfreien Grammatik mit μf z.B. die repräsentierte Sprache oder deren Parikh-Bild) dar. Zentrales Ergebnis der Dissertation ist eine Verallgemeinerung des Newtonschen Näherungsverfahrens: Es wird gezeigt, dass sich dieses Verfahren allgemein zur Approximation bzw. Bestimmung der kleinsten Lösung eines multivariaten polynomiellen Gleichungssystems über beliebigen w-stetigen Semiringen verwenden lässt. Das diesen Resultaten zugrundeliegende Beweisverfahren wird weiterhin verwendet, um für spezielle Unterklassen von w-stetigen Semiringen effizientere Verfahren nicht nur zur Approximation, sondern auch zur Bestimmung von μf herzuleiten. Anwendung finden diese Resultate u.a. in der Bestimmung des Parikh-Bilds kontextfreier Sprachen, der Analyse paralleler rekursiver Programme, stochastischer Prozesse, der Analyse der Performanz von Netzwerkalgorithmen.