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.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.359-370, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455344
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 10:43:52
Dernière modification le : mercredi 10 février 2010 - 10:44:18
Document(s) archivé(s) le : vendredi 18 juin 2010 - 17:54:05

Fichier

esparza.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455344, version 1

Collections

Citation

Javier Esparza, Andreas Gaiser, Stefan Kiefer. Computing Least Fixed Points of Probabilistic Systems of Polynomials. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.359-370, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455344〉

Partager

Métriques

Consultations de la notice

486

Téléchargements de fichiers

95