Synthesising Strategy Improvement and Recursive Algorithms for Solving 2. 5 Player Parity Games

2. 5 player parity games combine the challenges posed by 2. 5 player reachability games and the qualitative analysis of parity games. These two types of problems are best approached with different types of algorithms: strategy improvement algorithms for 2. 5 player reachability games and recursive algorithms for the qualitative analysis of parity games. We present a method that—in contrast to existing techniques—tackles both aspects with the best suited approach and works exclusively on the 2. 5 player game itself. The resulting technique is powerful enough to handle games with millions of states.

Authors

• Sven Schewe University of Liverpool

Keywords

No keywords are indexed for this paper.