Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Reduction of Stochastic Parity to Stochastic Mean-payoff Games

Krishnendu Chatterjee and Thomas A. Henzinger

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-140
November 6, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-140.pdf

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with \omega-regular winning conditions specified as parity objectives, and mean-payoff (or long-run average) objectives. These games lie in NP and coNP. We present a polynomial time Turing reduction of stochastic parity games to stochastic mean-payoff games.


BibTeX citation:

@techreport{Chatterjee:EECS-2006-140,
    Author = {Chatterjee, Krishnendu and Henzinger, Thomas A.},
    Title = {Reduction of Stochastic Parity to  Stochastic Mean-payoff Games},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Nov},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-140.html},
    Number = {UCB/EECS-2006-140},
    Abstract = {A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with \omega-regular winning conditions specified as parity objectives, and mean-payoff (or long-run average) objectives. These games lie in NP and coNP. We present a polynomial time Turing reduction of stochastic parity games to stochastic mean-payoff games.}
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu
%A Henzinger, Thomas A.
%T Reduction of Stochastic Parity to  Stochastic Mean-payoff Games
%I EECS Department, University of California, Berkeley
%D 2006
%8 November 6
%@ UCB/EECS-2006-140
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-140.html
%F Chatterjee:EECS-2006-140