Loading...
Please wait, while we are loading the content...
Similar Documents
Quantitative Stochastic Parity Games
| Content Provider | CiteSeerX |
|---|---|
| Author | Henzinger, Thomas A. Chatterjee, Krishnendu Jurdziński, Marcin |
| Abstract | We study perfect-information stochastic parity games. These are two-player nonterminating games which are played on a graph with turn-based probabilistic transitions. A play results in an infinite path and the conflicting goals of the two players are ω-regular path properties, formalized as parity winning conditions. The qualitative solution of such a game amounts to computing the set of vertices from which a player has a strategy to win with probability 1 (or with positive probability). The quantitative solution amounts to computing the value of the game in every vertex, i.e., the highest probability with which a player can guarantee satisfaction of his own objective in a play that starts from the vertex. For the important special case of one-player stochastic parity games (parity Markov decision processes) we give |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Play Result Quantitative Solution Amount Quantitative Stochastic Parity Game Conflicting Goal Turn-based Probabilistic Transition Qualitative Solution Two-player Nonterminating Game Perfect-information Stochastic Parity Game Regular Path Property Positive Probability One-player Stochastic Parity Game Infinite Path Parity Markov Decision Process Important Special Case |
| Content Type | Text |
