A reduction from parity games to simple stochastic games

K. Chatterjee, N. Fijalkow, in:, EPTCS, 2011, pp. 74–86.


Conference Paper | Published | English
Author
;
Department
Series Title
EPTCS
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.
Publishing Year
Date Published
2011-06-04
Volume
54
Page
74 - 86
Conference
GandALF: Games, Automata, Logic, and Formal Verification
Conference Location
Minori, Italy
Conference Date
2011-06-15 – 2011-06-17
IST-REx-ID

Cite this

Chatterjee K, Fijalkow N. A reduction from parity games to simple stochastic games. In: Vol 54. EPTCS; 2011:74-86. doi:10.4204/EPTCS.54.6
Chatterjee, K., & Fijalkow, N. (2011). A reduction from parity games to simple stochastic games (Vol. 54, pp. 74–86). Presented at the GandALF: Games, Automata, Logic, and Formal Verification, Minori, Italy: EPTCS. https://doi.org/10.4204/EPTCS.54.6
Chatterjee, Krishnendu, and Nathanaël Fijalkow. “A Reduction from Parity Games to Simple Stochastic Games,” 54:74–86. EPTCS, 2011. https://doi.org/10.4204/EPTCS.54.6.
K. Chatterjee and N. Fijalkow, “A reduction from parity games to simple stochastic games,” presented at the GandALF: Games, Automata, Logic, and Formal Verification, Minori, Italy, 2011, vol. 54, pp. 74–86.
Chatterjee K, Fijalkow N. 2011. A reduction from parity games to simple stochastic games. GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 54. 74–86.
Chatterjee, Krishnendu, and Nathanaël Fijalkow. A Reduction from Parity Games to Simple Stochastic Games. Vol. 54, EPTCS, 2011, pp. 74–86, doi:10.4204/EPTCS.54.6.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar