Publication

Reduction of stochastic parity to stochastic mean-payoff games

Thomas Henzinger
2008
Journal Articles

Abstract

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with w-regular winning conditions specified as parity objectives, and mean-payoff (or limit-average) objectives. These games lie in NP boolean AND coNP. We present a polynomial-time Turing reduction of stochastic parity games to stochastic mean-payoff games. (c) 2007 Published by Elsevier B.V.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Reduction of stochastic parity to stochastic mean-payoff games

Chat with Graph Search

A Spatiotemporal Analysis of Brain Dynamics, a New Feature for Sleep and Seizure State Discrimination

Implementing water recirculation in a novel portable plasma-activated water reactor enhances antimicrobial effect against Escherichia coli

Isogeny Problems with Level Structure