The Complexity of Partial-observation Stochastic Parity Games With Finite-memory Strategies
Authors:
Preprint
Abstract
We consider two-player partial-observation stochastic games on finite-state graphs 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). These qualtitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME. 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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Solving Partial-Information Stochastic Parity Games2013
- Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and SafraTheoretical Computer Science, 1995
- Infinite games played on finite graphsAnnals of Pure and Applied Logic, 1993
- Alternating automata on infinite treesTheoretical Computer Science, 1987
- The complexity of two-player games of incomplete informationJournal of Computer and System Sciences, 1984
- Introduction to Probabilistic Automata1971