%0 Conference Proceedings
%F lics09
%A Bertrand, N.
%A Genest, B.
%A H., Gimbert.
%T Qualitative Determinacy and Decidability of Stochastic Games with Signals
%B 24th Annual IEEE Symposium on Logic in Computer Science (LICS'09)
%P 319-328
%I IEEE Computer Society Press
%C Los Angeles, CA, USA
%X We consider the standard model of finite two-person zero-sum stochastic games with signals. We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Büchi or co-Büchi winning objectives. We prove two qualitative determinacy results. First, in a reachability game either player 1 can achieve almost-surely the reachability objective, or player 2 can ensure surely the complementary safety objective, or both players have positively winning strategies. Second, in a Büchi game if player 1 cannot achieve almost-surely the Büchi objective, then player 2 can ensure positively the complementary co-Büchi objective. We prove that players only need strategies with finite-memory, whose sizes range from no memory at all to doubly-exponential number of states, with matching lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing the finite memory strategy. Complexity ranges from EXPTIME to 2-EXPTIME with matching lower bounds, and better complexity can be achieved for some special cases where one of the players is better informed than her opponent
%U http://www.irisa.fr/vertecs/Publis/Ps/lics2009.pdf
%U http://dx.doi.org/10.1109/LICS.2009.31
%8 August
%D 2009