UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-05-1405.pdf
CSD-05-1405.ps
Conditions of Use

Archive Home Page

Stochastic Limit-Average Games are in EXPTIME

Authors:
Chatterjee, Krishnendu
Majumdar, Rupak
Henzinger, Thomas A.
Technical Report Identifier: CSD-05-1405
August 2005
CSD-05-1405.pdf
CSD-05-1405.ps

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.