==============================================
Title: "Adding Recursion to Markov Chains, Markov Decision Processes,
        and Stochastic Games."

Speaker:  Kousha Etessami,  University of Edinburgh

Abstract:

I will decribe a family of finitely presented, but infinite-state,
stochastic models that arise by adding a natural recursion feature
to Markov Chains, Markov Decision Processes, and Stochastic Games.

These stochastic models can be used as natural abstract models of probabilistic
procedural programs with recursion. They also subsume a number of other classic and
heavily studied stochastic models, including (multi-type) branching processes,
(quasi-)birth-death processes, stochastic context-free grammars, and others, and they are
expressively equivalent to probabilistic pushdown systems.

The theory behind the algorithmic analysis and model checking of these recursive
stochastic models, developed over the past few years, has turned out to be very rich,
with connections to a number of areas of research. I will survey just a few highlights
from this work.  Several key analysis algorithms have been implemented in a software tool
called PReMo
with positive results, and I may briefly discuss some of the practical
aspects of efficient implementation.

Finally, there remain many open questions about the computational complexity of basic
analysis problems for recursive stochastic models. I will highlight just a few such open
problems.

(Based on joint work with Mihalis Yannakakis, Columbia University,
 and with Dominik Wojtczak, University of Edinburgh (& CWI). )
================================================