---
res:
bibo_abstract:
- The theory of graph games is the foundation for modeling and synthesizing reactive
processes. In the synthesis of stochastic processes, we use 2 1/2-player games
where some transitions of the game graph are controlled by two adversarial players,
the System and the Environment, and the other transitions are determined probabilistically.
We consider 2 1/2-player games where the objective of the System is the conjunction
of a qualitative objective (specified as a parity condition) and a quantitative
objective (specified as a mean-payoff condition). We establish that the problem
of deciding whether the System can ensure that the probability to satisfy the
mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching
the best known bound in the special case of 2-player games (where all transitions
are deterministic). We present an algorithm running in time O(d·n2d·MeanGame)
to compute the set of almost-sure winning states from which the objective can
be ensured with probability 1, where n is the number of states of the game, d
the number of priorities of the parity objective, and MeanGame is the complexity
to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games.
Our results are useful in the synthesis of stochastic 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: Laurent
foaf_name: Doyen, Laurent
foaf_surname: Doyen
- foaf_Person:
foaf_givenName: Hugo
foaf_name: Gimbert, Hugo
foaf_surname: Gimbert
- foaf_Person:
foaf_givenName: Youssouf
foaf_name: Oualhadj, Youssouf
foaf_surname: Oualhadj
bibo_doi: 10.1007/978-3-642-54830-7_14
bibo_volume: 8412
dct_date: 2014^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Perfect-information stochastic mean-payoff parity games@
...