Strategy improvement and randomized subexponential algorithms for stochastic parity games Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A
Title: Strategy improvement and randomized subexponential algorithms for stochastic parity games
Title Series: LNCS
Affiliation
Abstract: A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.
Conference Title: STACS: Theoretical Aspects of Computer Science
Volume: 3884
Conference Dates: February 23-25, 2006
Conference Location: Marseille, France
ISBN: 978-3-540-67141-1
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2006-02-14
Start Page: 512
End Page: 523
DOI: 10.1007/11672142_42
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work