Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP



Mayr, Richard, Schewe, Sven ORCID: 0000-0002-9093-9518, Totzke, Patrick ORCID: 0000-0001-5274-8190 and Wojtczak, Dominik ORCID: 0000-0001-5560-0546
(2021) Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2021, 12650. pp. 427-447.

Access the full-text of this item by clicking on the Open Access link.
[thumbnail of 2101.06989v1.pdf] Text
2101.06989v1.pdf - Submitted version

Download (649kB) | Preview

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 \cap coNP$. The same holds for checking if such a $k$ exists and if a given $k$ is minimal.

Item Type: Article
Additional Information: timestamp: Fri, 14 May 2021 08:34:11 +0200 biburl: https://dblp.org/rec/conf/fossacs/MayrSTW21.bib bibsource: dblp computer science bibliography, https://dblp.org
Uncontrolled Keywords: Simple Stochastic Games, Parity Games, Energy Games
Depositing User: Symplectic Admin
Date Deposited: 26 Jan 2021 10:31
Last Modified: 29 Sep 2024 02:45
DOI: 10.1007/978-3-030-71995-1_22
Open Access URL: https://link.springer.com/chapter/10.1007/978-3-03...
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3114823