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



Hahn, Ernst Moritz, Schewe, Sven ORCID: 0000-0002-9093-9518, Turrini, Andrea and Zhang, Lijun
(2017) Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games. In: Verification, Model Checking, and Abstract Interpretation, 2017-1-15 - 2017-1-17, Paris.

[img] Text
vmcai_13.pdf - Author Accepted Manuscript

Download (362kB)

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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: cs.LO, cs.LO, cs.FL
Depositing User: Symplectic Admin
Date Deposited: 22 Feb 2017 10:37
Last Modified: 19 Jan 2023 07:19
DOI: 10.1007/978-3-319-52234-0_15
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3005467