A reduction from parity games to simple stochastic games Conference Paper

Author(s): Chatterjee, Krishnendu; Fijalkow, Nathanaël
Title: A reduction from parity games to simple stochastic games
Title Series: EPTCS
Affiliation IST Austria
Abstract: Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena.
Conference Title: GandALF: Games, Automata, Logic, and Formal Verification
Volume: 54
Conference Dates: June 15-17, 2011
Conference Location: Minori, Italy
ISBN: 2075-2180
Publisher: EPTCS  
Date Published: 2011-06-04
Start Page: 74
End Page: 86
Sponsor: The research was supported by Austrian Science Fund (FWF) NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.
DOI: 10.4204/EPTCS.54.6
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work