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

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/Archive/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},
    Year= {2006},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-140.html
%F Chatterjee:EECS-2006-140