A reduction from parity games to simple stochastic games

Computer Science – Computer Science and Game Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

In Proceedings GandALF 2011, arXiv:1106.0814

Scientific paper

10.4204/EPTCS.54.6

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A reduction from parity games to simple stochastic games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A reduction from parity games to simple stochastic games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A reduction from parity games to simple stochastic games will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-25253

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.