Abstract
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP∩coNP. The same holds for checking if such a k exists and if a given k is minimal.
Original language | English |
---|---|
Title of host publication | Proceedings of FOSSACS 2021 |
Publisher | Springer Berlin Heidelberg |
Number of pages | 39 |
Publication status | Accepted/In press - 18 Dec 2020 |
Event | 24th International Conference on Foundations of Software Science and Computation Structures - Online Duration: 27 Mar 2021 → 1 Apr 2021 https://etaps.org/2021/fossacs |
Conference
Conference | 24th International Conference on Foundations of Software Science and Computation Structures |
---|---|
Abbreviated title | FoSSaCS 2021 |
City | Online |
Period | 27/03/21 → 1/04/21 |
Internet address |