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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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
Editors	Ahmed Bouajjani, David Monniaux
Place of Publication	Cham
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 - 2017
Externally published	Yes
Event	18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017 - Paris, France Duration: 15 Jan 2017 → 17 Jan 2017 Conference number: 18

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10145
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017
Abbreviated title	VMCAI 2017
Country/Territory	France
City	Paris
Period	15/01/17 → 17/01/17

Keywords

Markov decision process (MDP)
Player game
Strategy improvement
Winning strategy
Correctness proof

Access to Document

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

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 A. Bouajjani, & D. Monniaux (Eds.), Verification, Model Checking, and Abstract Interpretation: 18th International Conference, VMCAI 2017, Paris, France, January 15–17, 2017, Proceedings (pp. 266-287). (Lecture Notes in Computer Science; Vol. 10145). Springer. https://doi.org/10.1007/978-3-319-52234-0_15

Hahn, Ernst Moritz ; Schewe, Sven ; Turrini, Andrea et al. / Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games. Verification, Model Checking, and Abstract Interpretation: 18th International Conference, VMCAI 2017, Paris, France, January 15–17, 2017, Proceedings. editor / Ahmed Bouajjani ; David Monniaux. Cham : Springer, 2017. pp. 266-287 (Lecture Notes in Computer Science).

@inproceedings{24f60a4933db4d3c9efa5ac9241d6a6c,

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 (MDP), Player game, Strategy improvement, Winning strategy, Correctness proof",

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

year = "2017",

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

language = "English",

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

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "266--287",

editor = "Ahmed Bouajjani and David Monniaux",

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

address = "Germany",

note = "18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017, VMCAI 2017 ; Conference date: 15-01-2017 Through 17-01-2017",

}

Hahn, EM, Schewe, S, Turrini, A & Zhang, L 2017, Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games. in A Bouajjani & D Monniaux (eds), Verification, Model Checking, and Abstract Interpretation: 18th International Conference, VMCAI 2017, Paris, France, January 15–17, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10145, Springer, Cham, pp. 266-287, 18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017, Paris, France, 15/01/17. https://doi.org/10.1007/978-3-319-52234-0_15

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. ed. / Ahmed Bouajjani; David Monniaux. Cham: Springer, 2017. p. 266-287 (Lecture Notes in Computer Science; Vol. 10145).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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

N1 - Conference code: 18

PY - 2017

Y1 - 2017

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 (MDP)

KW - Player game

KW - Strategy improvement

KW - Winning strategy

KW - Correctness proof

UR - https://www.scopus.com/pages/publications/85010703330

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

T3 - Lecture Notes in Computer Science

SP - 266

EP - 287

BT - Verification, Model Checking, and Abstract Interpretation

A2 - Bouajjani, Ahmed

A2 - Monniaux, David

PB - Springer

CY - Cham

T2 - 18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017

Y2 - 15 January 2017 through 17 January 2017

ER -

Hahn EM, Schewe S, Turrini A, Zhang L. Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games. In Bouajjani A, Monniaux D, editors, Verification, Model Checking, and Abstract Interpretation: 18th International Conference, VMCAI 2017, Paris, France, January 15–17, 2017, Proceedings. Cham: Springer. 2017. p. 266-287. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-52234-0_15

Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this