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

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

doi:10.1007/978-3-319-52234-0_15

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 proceeding › Conference contribution

2 Citations (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 language	English
Title of host publication	Verification, Model Checking, and Abstract Interpretation
Subtitle of host publication	18th International Conference, VMCAI 2017, Paris, France, January 15-17, 2017, Proceedings
Publisher	Springer
Pages	266-287
Number of pages	22
ISBN (Electronic)	978-3-319-52234-0
ISBN (Print)	978-3-319-52233-3
DOIs	https://doi.org/10.1007/978-3-319-52234-0_15
Publication status	Published - 01 Feb 2017
Externally published	Yes

Keywords

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

Access to Document

10.1007/978-3-319-52234-0_15Licence: Unspecified

Cite this

Hahn, E. M., Schewe, S., Turrini, A., & Zhang, L. (2017). Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games. In Verification, Model Checking, and Abstract Interpretation : 18th International Conference, VMCAI 2017, Paris, France, January 15-17, 2017, Proceedings (pp. 266-287). Springer. https://doi.org/10.1007/978-3-319-52234-0_15

@inproceedings{da2e0a71b74c4b16a0201cac5e870cad,

title = "Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games",

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.",

keywords = "Markov Decision Process, 2.5 Player Game, Strategy Improvement, Winning Strategy, Correctness Proof",

author = "Hahn, {Ernst Moritz} and Sven Schewe and Andrea Turrini and Lijun Zhang",

year = "2017",

month = feb,

day = "1",

doi = "10.1007/978-3-319-52234-0_15",

language = "English",

isbn = "978-3-319-52233-3",

pages = "266--287",

booktitle = "Verification, Model Checking, and Abstract Interpretation",

publisher = "Springer",

}

Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games. / Hahn, Ernst Moritz; Schewe, Sven; Turrini, Andrea et al.
Verification, Model Checking, and Abstract Interpretation : 18th International Conference, VMCAI 2017, Paris, France, January 15-17, 2017, Proceedings. Springer, 2017. p. 266-287.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Hahn, Ernst Moritz

AU - Schewe, Sven

AU - Turrini, Andrea

AU - Zhang, Lijun

PY - 2017/2/1

Y1 - 2017/2/1

N2 - 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.

AB - 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.

KW - Markov Decision Process

KW - 2.5 Player Game

KW - Strategy Improvement

KW - Winning Strategy

KW - Correctness Proof

U2 - 10.1007/978-3-319-52234-0_15

DO - 10.1007/978-3-319-52234-0_15

M3 - Conference contribution

SN - 978-3-319-52233-3

SP - 266

EP - 287

BT - Verification, Model Checking, and Abstract Interpretation

PB - Springer

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this