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

Richard Mayr, Sven Schewe, Patrick Totzke, Dominik Wojtczak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationProceedings of FOSSACS 2021
PublisherSpringer Berlin Heidelberg
Number of pages39
Publication statusAccepted/In press - 18 Dec 2020
Event24th International Conference on Foundations of Software Science and Computation Structures - Online
Duration: 27 Mar 20211 Apr 2021
https://etaps.org/2021/fossacs

Conference

Conference24th International Conference on Foundations of Software Science and Computation Structures
Abbreviated titleFoSSaCS 2021
CityOnline
Period27/03/211/04/21
Internet address

Fingerprint Dive into the research topics of 'Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP'. Together they form a unique fingerprint.

Cite this