Solving systems of positive polynomial equations [Elektronische Ressource] / Stefan Kiefer

¨ ¨TECHNISCHE UNIVERSITAT MUNCHENLehrstuhl fu¨r Informatik VIISolving Systems ofPositive Polynomial EquationsStefan KieferVollst¨andiger Abdruck der von der Fakult¨at fur¨ Informatik der Technischen Universita¨tMunc¨ hen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr. H. SeidlPruf¨ er der Dissertation: 1. Univ.-Prof. Dr. F.J. Esparza Estaun2. Univ.-Prof. Dr. H.-J. BungartzDie Dissertation wurde am 25.06.2009 bei der Technischen Universit¨at Munc¨ hen eingereichtund durch die Fakult¨at fur¨ Informatik am 02.10.2009 angenommen.AbstractIn this thesis, we consider equation systems of the formX = f (X ,...,X )1 1 1 n...X = f (X ,...,X )n n 1 nwhere f (X ,...,X ) is, for all i ∈ {1,...,n}, an expression built up from real-valuedi 1 nvariablesX ,...,X ,nonnegativerealconstants,andtheoperatorsmultiplication,addition,1 nminimum and maximum. We call such an equation system positive and denote it in vectorform by X =f(X). The least solution is called μ, i.e., μ is the least fixed point of f.Positive equation systems appear naturally in the analysis of stochastic models likestochastic context-free grammars (with numerous applications to natural language process-ingandcomputationalbiology), probabilisticprogramswithprocedures,web-surfingmodelswith back buttons, branching processes, and termination games.