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

Richard Mayr; Sven Schewe; Patrick Totzke; Dominik Wojtczak

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 proceeding › Conference 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 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	https://etaps.org/2021/fossacs

Access to Document

2101.06989Accepted author manuscript, 635 KBLicence: Creative Commons: Attribution (CC-BY)

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

@inproceedings{56be7ec7798941b581de37e6325e9805,

title = "Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP",

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. ",

author = "Richard Mayr and Sven Schewe and Patrick Totzke and Dominik Wojtczak",

note = "Proceedings of FOSSACS 2021. https://etaps.org/2021/fossacs; 24th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2021 ; Conference date: 27-03-2021 Through 01-04-2021",

year = "2020",

month = dec,

day = "18",

language = "English",

booktitle = "Proceedings of FOSSACS 2021",

publisher = "Springer Berlin Heidelberg",

url = "https://etaps.org/2021/fossacs",

}

TY - GEN

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

AU - Mayr, Richard

AU - Schewe, Sven

AU - Totzke, Patrick

AU - Wojtczak, Dominik

N1 - Proceedings of FOSSACS 2021. https://etaps.org/2021/fossacs

PY - 2020/12/18

Y1 - 2020/12/18

N2 - 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.

AB - 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.

UR - https://arxiv.org/abs/2101.06989

M3 - Conference contribution

BT - Proceedings of FOSSACS 2021

PB - Springer Berlin Heidelberg

T2 - 24th International Conference on Foundations of Software Science and Computation Structures

Y2 - 27 March 2021 through 1 April 2021

ER -