Lösen polynomieller Gleichungssysteme über Semiringen
| dc.contributor.author | Luttenberger, Michael | |
| dc.contributor.editor | Hölldobler, Steffen | |
| dc.date.accessioned | 2020-08-21T08:46:22Z | |
| dc.date.available | 2020-08-21T08:46:22Z | |
| dc.date.issued | 2011 | |
| dc.description.abstract | 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. | de |
| dc.identifier.isbn | 978-3-88579-415-8 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/33768 | |
| dc.language.iso | de | |
| dc.publisher | Gesellschaft für Informatik | |
| dc.relation.ispartof | Ausgezeichnete Informatikdissertationen 2010 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Dissertations, Volume D-11 | |
| dc.title | Lösen polynomieller Gleichungssysteme über Semiringen | de |
| gi.citation.endPage | 220 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 211 |
Dateien
Originalbündel
1 - 1 von 1