Probabilities and partial observation: from probabilistic omega automata to stochastic games of imperfect information

Nathalie Bertrand ( INRIA )

Recently, models with probabilities and partial observation have attracted attention in the verification community. In this talk we will expose basic results and open questions for (at least) two instances of such models. To start with, we consider probabilistic omega automata, and prominently probabilistic Büchi automata (PBA), and draw the decidability frontier for various language decision problems. We then move to stochastic games of imperfect information, which can be seen as a 2-player extension of PBA, and explain how the results can be generalized.