Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Solving Parity Games on Integer Vectors
Authors: Richard Mayr ; Parosh Aziz Abdulla ; Arnaud Sangnier ; Jeremy Sproston
Date:Aug 2013
Publication Title:CONCUR 2013
Publication Type:Conference Paper Publication Status:Published
We consider parity games on infinite graphs where configurations are represented by control-states and integer vectors. This framework subsumes two classic game problems: parity games on vector addition systems with states (vass) and multidimensional energy parity games. We show that the multidimensional energy parity game problem is inter-reducible with a subclass of single-sided parity games on vass where just one player can modify the integer counters and the opponent can only change control-states. Our main result is that the minimal elements of the upward-closed winning set of these single-sided parity games on vass are computable. This implies that the Pareto frontier of the minimal initial credit needed to win multidimensional energy parity games is also computable, solving an open question from the literature. Moreover, our main result implies the decidability of weak simulation preorder/equivalence between finite-state systems and vass, and the decidability of model checking vass with a large fragment of the modal mu-calculus.
Links To Paper
Full version with all proofs
Bibtex format
author = { Richard Mayr and Parosh Aziz Abdulla and Arnaud Sangnier and Jeremy Sproston },
title = {Solving Parity Games on Integer Vectors},
book title = {CONCUR 2013},
year = 2013,
month = {Aug},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh