Solving polynomial systems on semirings [Elektronische Ressource] : a generalization of Newton's method / Michael Luttenberger

Sujets

• Wissenschaft

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 29
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

TECHNISCHE UNIVERSITAT MUNCHEN
Lehrstuhl fur Informatik VII
Solving Polynomial Systems on Semirings:
A Generalization of Newton’s Method
Michael Luttenberger
Vollst andiger Abdruck der von der Fakult at fur Informatik der Technischen
Universit at Munc hen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. T. Nipkow, Ph.D.
Prufer der Dissertation: 1. Univ.-Prof. Dr. F. J. Esparza Estaun
2. Dr. V. Diekert,
Universit at Stuttgart
Die Dissertation wurde am 25.06.2009 bei der Technischen Universit at-
Munc hen eingereicht und durch die Fakult at fur Informatik am 02.02.2010
angenommen.thLAT Xed on Friday 5 March, 2010, 10:37EZusammenfassung
Polynomielle Systeme ub er Semiringen treten in verschiedenen Bereichen der Infor-
matik auf, so z.B. in der statischen Analyse prozeduraler Programme oder der The-
orie formaler Sprachen. In dieser Dissertation wird ein neues Verfahren zur Berech-
nung des kleinsten Fixpunkts polynomieller Systeme vorgeschlagen. Hierbei han-
delt es sich um eine Verallgemeinerung des wohlbekannten Newton-Verfahrens zur
Approximation von Nullstellen nichtlinearer Funktionen uber den reellen Zahlen
durch iterative Linearisierung. Es wird gezeigt, dass die vorgestellte Verallge-
meinerung des Newton-Verfahrens mindestens genauso schnell gegen den kleinsten
Fixpunkt konvergiert wie die ublic he Fixpunktiteration. Weiterhin werden mehrere
Klassen von Semiringen identi ziert, fur welche das verallgemeinerte Newton-
Verfahren, im Gegensatz zu der gew ohnlichen Fixpunktiteration, den kleinsten
Fixpunkt bereits nach einer endlichen Anzahl von Iterationen erreicht. Schlie lich
ergeben sich aus diesen Konvergenzresultaten interessante Querbeziehungen zu
anderen Themen aus dem Bereich der formalen Sprachen, wie z.B. Sprachen von
endlichem Index oder dem Satz von Parikh.
Ausgehend von den Klassen von Semiringen, ub er welchen das verallgemeinerte
Newton-Verfahren bereits nach endlich vielen Schritten den kleinsten Fixpunkt
erreicht, werden in der Dissertation noch drei weitere Typen von Semiringen
vorgestellt, welche es gestatten, den kleinsten Fixpunkt durch eine endliche Anzahl
von Linearisierungen zu bestimmen. Hierbei erlauben es zwei der drei vorgestellten
Semiringklassen den kleinsten Fixpunkt nur mit Hilfe einer Linearisierung bereits
zu bestimmen, w ahrend im Fall der dritten Klasse auf eine Linearisierung ganz
verzichtet werden kann.
Abschlie end werden in der Dissertation noch Min-Max-Systeme betrachtet.
Disese stellen eine naturlic he Erweiterung polynomieller Systeme ub er total-
geordneten Semiringen dar. Es wird eine Klasse von Semiringen vorgestellt, die
es erlaubt, nichtlineare Min-Max-Systeme mit Hilfe des bekannten Ansatzes der
Strategieieration, erweitert auf nichtdeterministische Strategien, zuosen.l Abstract
Systems of polynomials on semirings arise in several branches of computer science,
like static analysis of procedural programs or formal language theory. We propose
a new technique for calculating the least xed points of such polynomial systems.
This tec is a generalization of Newton’s method, the well-known method
for approximating a zero of a nonlinear function on the reals. We show that
our generalization of Newton’s method converges at least as fast as the standard
xed point iteration, and identify classes of semirings on which Newton’s method
even reaches the least xed point after a nite number of steps in contrast to the
standard xed point iteration. We further obtain from these convergence results
interesting links to other topics of formal language theory, for instance, languages
of nite index and the Parikh theorem.
Motivated by our results on the convergence of Newton’s method, we then identify
three more classes of semirings which allow for an even faster calculation of the
least xed point. Two of these semirings allow for reducing a nonlinear polynomial
system to a linear system in such a way that the least xed point is preserved. In
the third case already a nite number of standard xed point iterations su ce to
calculate the least xed point, although this class of semirings does not satisfy the
ascending chain condition.
We then turn to min-max-systems, a natural generalization of polynomial systems
on semirings whose natural order is total. We identify a class of semirings which
allow to solve nonlinear min-max-systems by the established approach of strat-
egy iteration. In particular, we consider strategy iteration using nondeterministic
strategies and show that these strategies allow for choosing an optimal successor.Acknowledgments
First of all, I want to thank my parents and my sister for supporting and en-
couraging me through all these years and for giving me the opportunity to focus
exclusively on school and university. This thesis would not have been possible
without their support .
I would also like to thank Prof. Volker Diekert. He supported me in numerous ways
while I was still studying at the University of Stuttgart, supervised my diploma
thesis and introduced me to my supervisor Prof. Javier Esparza when I was looking
for a position as a Ph.D. student.
In particular, I have to thank Javier for introducing me to an interesting research
topic and for guiding and supporting my research. I also would like to thank him
as he always takes the time to listen to you, your ideas or problems. I have learned
that this is not a matter of course. <muchas gracias! Finally, thanks to Javier I
have had the pleasure to work with an extraordinary group of people over the last
ve years:
For example, Stefan Schwoon, the only person I know who can optimize a bicycle
tour w.r.t. several target functions, like total length, number of sights along the
trip, or total time, and he can do this remarkably faster than google maps! Tobias
Heindel, who began his Ph.D. studies at our department back in Stuttgart at the
same time as I did, and with whom I have shared the sorrows most beginning
Ph.D. students have. I would also like to mention Claus Schr oter in whose o ce I
wasted uncounted hours discussing music. Dejvuth Suwimonteerabuth aka Remy
courageously endured my nonsense on the way to and back from the university
here in Munich for the last three years (Dauerwelle vs. Minipli!). In particular,
I am indebted to Stefan Kiefer aka Mr. Pinetree. Many of the results presented
in this thesis were obtained in collaboration with him and Javier. Apart from
that, Stefan may be the only person on this planet who has physically experienced
Moshe Vardi resolving a deadlock. Thanks to these guys, my new colleagues here
at the university of Munich (J org-einiges-geht, Andreas, Christian, Stefan, and
the guys now at the university of Darmstadt) and, of course, Javier, I will always
enjoy remembering this time of my life.
Of course, the list of people I feel, or should feel, indebted to is by no means
complete. Therefore, a big thank you to my family in Tauberbischofsheim and my
friends back in Stuttgart.Contents
1 Introduction 1
1.1 Interprocedural Data ow-Analysis . . . . . . . . . . . . . . . . 1
1.1.1 From Semilattices to Semirings . . . . . . . . . . . . . 5
1.2 Solving Systems of Equations . . . . . . . . . . . . . . . . . . 15
1.3 Contribution and Related Work . . . . . . . . . . . . . . . . . 16
1.4 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2 Preliminaries 21
2.1 Basic De nitions and Notations . . . . . . . . . . . . . . . . . 21
2.2 !-Continuous Semirings . . . . . . . . . . . . . . . . . . . . . 24
3 Newton’s Method on !-Continuous Semirings 33
3.1 Generalizing Newton’s Method . . . . . . . . . . . . . . . . . . 33
3.1.1 The Univariate Case . . . . . . . . . . . . . . . . . . . 33
3.1.2 The Multivariate Case . . . . . . . . . . . . . . . . . . 38
3.1.3 Fundamental Properties of the Newton Sequences . . . 40
3.1.4 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Derivation Trees and the Newton Approximants . . . . . . . . 47
3.2.1 Kleene Sequence and Height . . . . . . . . . . . . . . . 49
3.2.2 Newton and Dimension . . . . . . . . . . . . 50
3.3 Idempotent Semirings . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Language Semirings . . . . . . . . . . . . . . . . . . . . 55
3.4 Commutative Idempotent Semirings . . . . . . . . . . . . . . . 56
3.4.1 Analysis of the Convergence Speed . . . . . . . . . . . 57
3.4.2 Generalization to Commutative Kleene Algebras . . . . 61
3.4.3 Comparison with previous proofs of Parikh’s theorem . 64
3.5 Non-Distributive Program Analyses . . . . . . . . . . . . . . . 65
4 Derivation Tree Analysis 71
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.2 Bamboos and their Yield . . . . . . . . . . . . . . . . . . . . . 73
4.3 Star-Distributive Semirings . . . . . . . . . . . . . . . . . . . . 74
4.3.1 The (min; +)-Semiring . . . . . . . . . . . . . . . . . . 76
4.3.2 Throughput of Grammars . . . . . . . . . . . . . . . . 77
4.4 Lossy Semirings . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.5 1-bounded Semirings . . . . . . . . . . . . . . . . . . . . . . . 81
5 Min-Max-Systems and Strategy Iteration 83
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 on Totally Ordered cio-Semirings