The complexity of partial-observation stochastic parity games with finite-memory strategies

Chatterjee, Krishnendu and Doyen, Laurent and Nain, Sumit and Vardi, Moshe Y (2013) The complexity of partial-observation stochastic parity games with finite-memory strategies. Technical Report. IST Austria.

[img] Text
main-tech-rpt.pdf - Published Version
Available under License All rights reserved.
[IST-2013-141-v1+1]
Download (158Kb)

Abstract

We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are $\omega$-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis.

Item Type: Monograph (Technical Report)
Additional Information: A short version of this technical report is available at http://dx.doi.org/10.1007/978-3-642-54830-7_16
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
Research Group: Chatterjee Group
Depositing User: Prof Krishnendu Chatterjee
Date Deposited: 12 Sep 2013 08:12
Last Modified: 15 Jul 2019 14:45
URI: https://repository.ist.ac.at/id/eprint/141

Actions (login required)

View Item View Item