Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Stochastic Limit-Average Games are in EXPTIME

Krishnendu Chatterjee, Rupak Majumdar and Thomas A. Henzinger

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1405
August 2005

http://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5247.html
%F Chatterjee:CSD-05-1405