Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games

Ernst Moritz Hahn, Sven Schewe, Andrea Turrini, Lijun Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

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 several million states.
Original languageEnglish
Title of host publicationVerification, Model Checking, and Abstract Interpretation
Subtitle of host publication18th International Conference, VMCAI 2017, Paris, France, January 15-17, 2017, Proceedings
PublisherSpringer
Pages266-287
Number of pages22
ISBN (Electronic)978-3-319-52234-0
ISBN (Print)978-3-319-52233-3
DOIs
Publication statusPublished - 01 Feb 2017
Externally publishedYes

Keywords

  • Markov Decision Process
  • 2.5 Player Game
  • Strategy Improvement
  • Winning Strategy
  • Correctness Proof

Cite this