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

We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative [Formula: see text] -regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure prob...

Descripción completa

Detalles Bibliográficos
Autores principales: Mayr, Richard, Schewe, Sven, Totzke, Patrick, Wojtczak, Dominik
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2021
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984109/
http://dx.doi.org/10.1007/978-3-030-71995-1_22
_version_ 1783668007481901056
author Mayr, Richard
Schewe, Sven
Totzke, Patrick
Wojtczak, Dominik
author_facet Mayr, Richard
Schewe, Sven
Totzke, Patrick
Wojtczak, Dominik
author_sort Mayr, Richard
collection PubMed
description We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative [Formula: see text] -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 [Formula: see text] . The same holds for checking if such a k exists and if a given k is minimal.
format Online
Article
Text
id pubmed-7984109
institution National Center for Biotechnology Information
language English
publishDate 2021
record_format MEDLINE/PubMed
spelling pubmed-79841092021-03-23 Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP Mayr, Richard Schewe, Sven Totzke, Patrick Wojtczak, Dominik Foundations of Software Science and Computation Structures Article We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative [Formula: see text] -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 [Formula: see text] . The same holds for checking if such a k exists and if a given k is minimal. 2021-03-23 /pmc/articles/PMC7984109/ http://dx.doi.org/10.1007/978-3-030-71995-1_22 Text en © The Author(s) 2021 Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made. The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
spellingShingle Article
Mayr, Richard
Schewe, Sven
Totzke, Patrick
Wojtczak, Dominik
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title_full Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title_fullStr Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title_full_unstemmed Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title_short Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
title_sort simple stochastic games with almost-sure energy-parity objectives are in np and conp
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7984109/
http://dx.doi.org/10.1007/978-3-030-71995-1_22
work_keys_str_mv AT mayrrichard simplestochasticgameswithalmostsureenergyparityobjectivesareinnpandconp
AT schewesven simplestochasticgameswithalmostsureenergyparityobjectivesareinnpandconp
AT totzkepatrick simplestochasticgameswithalmostsureenergyparityobjectivesareinnpandconp
AT wojtczakdominik simplestochasticgameswithalmostsureenergyparityobjectivesareinnpandconp

Ejemplares similares