| Autor: |
Krishnendu Chatterjee, Nathanaël Fijalkow |
| Jazyk: |
angličtina |
| Rok vydání: |
2011 |
| Předmět: |
|
| Zdroj: |
Electronic Proceedings in Theoretical Computer Science, Vol 54, Iss Proc. GandALF 2011, Pp 74-86 (2011) |
| Druh dokumentu: |
article |
| ISSN: |
2075-2180 |
| DOI: |
10.4204/EPTCS.54.6 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
