Totzke, Patrick 
ORCID: 0000-0001-5274-8190, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik ORCID: 0000-0001-5560-0546
(2021)
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP.
In: Foundations of Software Science and Computation Structures, 2021-3-27 - 2021-4-1, Luxembourg.
Abstract
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω$$\omega $$-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$$\mathsf {NP}\cap \mathsf {coNP}$$. The same holds for checking if such a k exists and if a given k is minimal.
| Item Type: | Conference Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | 46 Information and Computing Sciences, 7 Affordable and Clean Energy |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Nov 2021 08:30 |
| Last Modified: | 13 May 2025 17:50 |
| DOI: | 10.1007/978-3-030-71995-1_22 |
| Open Access URL: | https://link.springer.com/chapter/10.1007%2F978-3-... |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3143104 |
Altmetric
Altmetric