Local Strategy Improvement for Parity Game Solving

Details Local Strategy Improvement for Parity Game Solving Local Strategy Improvement for Parity Game Solving

2010-06-08

arxiv.org/abs/1006.1409v1

EPTCS 25, 2010, pp. 118-131

Computer Science

Computer Science and Game Theory

Scientific paper

10.4204/EPTCS.25.13

The problem of solving a parity game is at the core of many problems in model checking, satisfiability checking and program synthesis. Some of the best algorithms for solving parity game are strategy improvement algorithms. These are global in nature since they require the entire parity game to be present at the beginning. This is a distinct disadvantage because in many applications one only needs to know which winning region a particular node belongs to, and a witnessing winning strategy may cover only a fractional part of the entire game graph. We present a local strategy improvement algorithm which explores the game graph on-the-fly whilst performing the improvement steps. We also compare it empirically with existing global strategy improvement algorithms and the currently only other local algorithm for solving parity games. It turns out that local strategy improvement can outperform these others by several orders of magnitude.

Affiliated with

Also associated with

No associations

Rating

Local Strategy Improvement for Parity Game Solving 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 Local Strategy Improvement for Parity Game Solving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Strategy Improvement for Parity Game Solving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-29321