Computing Least Fixed Points of Probabilistic Systems of Polynomials - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Computing Least Fixed Points of Probabilistic Systems of Polynomials

Javier Esparza
  • Fonction : Auteur correspondant
  • PersonId : 867111

Connectez-vous pour contacter l'auteur
Andreas Gaiser
  • Fonction : Auteur
  • PersonId : 867112
Stefan Kiefer
  • Fonction : Auteur
  • PersonId : 867113

Résumé

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.
Fichier principal
Vignette du fichier
esparza.pdf (232.94 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00455344 , version 1 (10-02-2010)

Identifiants

  • HAL Id : inria-00455344 , version 1

Citer

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⟩

Collections

STACS2010
337 Consultations
147 Téléchargements

Partager

Gmail Facebook X LinkedIn More