Krishnendu Chatterjee, Rupak Majumdar and Thomas A. Henzinger
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1405
August 2005
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1405.pdf
The value of a finite-state stochastic game with limit-average objectives can be approximated to within epsilon in time exponential in the size of the game and logarithmic in 1/epsilon.
BibTeX citation:
@techreport{Chatterjee:CSD-05-1405, Author = {Chatterjee, Krishnendu and Majumdar, Rupak and Henzinger, Thomas A.}, Title = {Stochastic Limit-Average Games are in EXPTIME}, Institution = {EECS Department, University of California, Berkeley}, Year = {2005}, Month = {Aug}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5247.html}, Number = {UCB/CSD-05-1405}, Abstract = {The value of a finite-state stochastic game with limit-average objectives can be approximated to within epsilon in time exponential in the size of the game and logarithmic in 1/epsilon.} }
EndNote citation:
%0 Report %A Chatterjee, Krishnendu %A Majumdar, Rupak %A Henzinger, Thomas A. %T Stochastic Limit-Average Games are in EXPTIME %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1405 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5247.html %F Chatterjee:CSD-05-1405