---
res:
bibo_abstract:
- 'Graph games provide the foundation for modeling and synthesis of reactive processes.
Such games are played over graphs where the vertices are controlled by two adversarial
players. We consider graph games where the objective of the first player is the
conjunction of a qualitative objective (specified as a parity condition) and a
quantitative objective (specified as a meanpayoff condition). There are two variants
of the problem, namely, the threshold problem where the quantitative goal is to
ensure that the mean-payoff value is above a threshold, and the value problem
where the quantitative goal is to ensure the optimal mean-payoff value; in both
cases ensuring the qualitative parity objective. The previous best-known algorithms
for game graphs with n vertices, m edges, parity objectives with d priorities,
and maximal absolute reward value W for mean-payoff objectives, are as follows:
O(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for the value problem.
Our main contributions are faster algorithms, and the running times of our algorithms
are as follows: O(nd-1 · m ·W) for the threshold problem, and O(nd · m · W · log(n
· W)) for the value problem. For mean-payoff parity objectives with two priorities,
our algorithms match the best-known bounds of the algorithms for mean-payoff games
(without conjunction with parity objectives). Our results are relevant in synthesis
of reactive systems with both functional requirement (given as a qualitative objective)
and performance requirement (given as a quantitative objective).@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Monika
foaf_name: Henzinger, Monika
foaf_surname: Henzinger
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Svozil, Alexander
foaf_surname: Svozil
bibo_doi: 10.4230/LIPIcs.MFCS.2017.39
bibo_volume: 83
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-395977046-0
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Faster algorithms for mean payoff parity games@
...