




Publications  Approximative Methods for Monotone Systems of minmaxPolynomial Equations





Reference:
Javier Esparza, Thomas Gawlitza, Stefan Kiefer, and Helmut Seidl. Approximative methods for monotone systems of minmaxpolynomial equations. In Luca Aceto et al., editor, Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), part I, volume 5125 of LNCS, pages 698–710, Reykjavik, Iceland, 2008. Springer.
Abstract:
A monotone system of minmaxpolynomial equations (minmaxMSPE) over the variables X_1, ..., X_n has for every i exactly one equation of the form X_i = f_i(X_1, ..., X_n) where each f_i(X_1, ..., X_n) is an expression built up from polynomials with nonnegative coefficients, minimum and maximumoperators. The question of computing least solutions of minmaxMSPEs arises naturally in the analysis of recursive stochastic games. MinmaxMSPEs generalize MSPEs for which convergence speed results of Newton's method have been established in previous papers. We present the first methods for approximatively computing least solutions of minmaxMSPEs which converge at least linearly. Whereas the first one converges faster, a single step of the second method is cheaper. Furthermore, we compute epsilonoptimal positional strategies for the player who wants to maximize the outcome in a recursive stochastic game.
Suggested BibTeX entry:
@inproceedings{EGKS08:icalp,
address = {Reykjavik, Iceland},
author = {Javier Esparza and Thomas Gawlitza and Stefan Kiefer and Helmut Seidl},
booktitle = {Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), part I},
editor = {Luca Aceto et al.},
pages = {698710},
publisher = {Springer},
series = {LNCS},
title = {Approximative Methods for Monotone Systems of minmaxPolynomial Equations},
volume = {5125},
year = {2008}
}




