2026-07-22T21:25:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2468 2024-03-06T10:33:24Z ddc:004 open_access

Computing Least Fixed Points of Probabilistic Systems of Polynomials Esparza, Javier Gaiser, Andreas Kiefer, Stefan Computing fixed points numerical approximation stochastic models branching processes We study systems of equations of the form $X_1 = f_1(X_1, \ldots, X_n), \ldots, X_n = f_n(X_1, \ldots, X_n)$ where each $f_i$ is a polynomial with nonnegative coefficients that add up to~$1$. The least nonnegative solution, say~$\mu$, of such equation systems is central to problems from various areas, like physics, biology, computational linguistics and probabilistic program verification. We give a simple and strongly polynomial algorithm to decide whether $\mu=(1,\ldots,1)$ holds. Furthermore, we present an algorithm that computes reliable sequences of lower and upper bounds on~$\mu$, converging linearly to~$\mu$. Our algorithm has these features despite using inexact arithmetic for efficiency. We report on experiments that show the performance of our algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Javier Esparza and Andreas Gaiser and Stefan Kiefer 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2468 urn:nbn:de:0030-drops-24685 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2468 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode