Computing Least Fixed Points of Probabilistic Systems of Polynomials

Details Computing Least Fixed Points of Probabilistic Systems of Polynomials Computing Least Fixed Points of Probabilistic Systems of Polynomials

2009-12-21

arxiv.org/abs/0912.4226v2

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS) 2010

Computer Science

Data Structures and Algorithms

Published in the Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS). Technical

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing Least Fixed Points of Probabilistic Systems of Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Least Fixed Points of Probabilistic Systems of Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Least Fixed Points of Probabilistic Systems of Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303168