Skip to Main content Skip to Navigation
Conference papers

Computing Least Fixed Points of Probabilistic Systems of Polynomials

Abstract : We study systems of equations of the form X1 = f1(X1, ..., Xn), ..., Xn = fn(X1, ..., Xn), where each fi 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, ..., 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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:43:52 AM
Last modification on : Wednesday, February 10, 2010 - 10:44:18 AM
Long-term archiving on: : Friday, June 18, 2010 - 5:54:05 PM


Files produced by the author(s)


  • HAL Id : inria-00455344, version 1



Javier Esparza, Andreas Gaiser, Stefan Kiefer. Computing Least Fixed Points of Probabilistic Systems of Polynomials. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.359-370. ⟨inria-00455344⟩



Record views


Files downloads