## Breadcrumb

# Probability and Recursion

Date

## Topic

Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of
Computer Science at Columbia University. Prior to joining Columbia, he
was Director of the Computing Principles Research Department at Bell
Labs (1991-2001) and at Avaya Labs (2001-2002), and Professor of
Computer Science at Stanford University (2002-2003). Dr. Yannakakis
received his PhD from Princeton University in 1979. His research
interests include algorithms, complexity, optimization, databases,
testing and verification. He has served on the editorial boards of
several journals, including as the past editor-in-chief of the SIAM
Journal on Computing, and has chaired various conferences, including
the IEEE Symposium on Foundations of Computer Science, the ACM
Symposium on Theory of Computing and the ACM Symposium on Principles of
Database Systems. Dr. Yannakakis is a Fellow of the ACM and of Bell
Labs, and a recipient of the Knuth Prize.

Abstract: We discuss recent work on the modeling and algorithmic analysis of systems involving recursion and probability. Recursive Markov chains extend ordinary finite state Markov chains with the ability to invoke other Markov chains in a potentially recursive manner. They offer a natural abstract model of probabilistic programs with procedures, and generalize other classical well-studied stochastic models, eg. Branching Processes and Stochastic Context-free Grammars, that have been used in a variety of areas. Recursive Markov Decision Processes and Stochastic Games similarly extend ordinary finite decision processes and games, and they are natural models for recursive systems involving both probabilistic and nonprobabilistic (controlled) actions. In a series of recent papers with Kousha Etessami (U. of Edinburgh), we have introduced these models and studied central algorithmic problems regarding questions of termination, reachability, and analysis of the properties of their executions. In this talk we will present some of the basic theory and algorithms.

Abstract: We discuss recent work on the modeling and algorithmic analysis of systems involving recursion and probability. Recursive Markov chains extend ordinary finite state Markov chains with the ability to invoke other Markov chains in a potentially recursive manner. They offer a natural abstract model of probabilistic programs with procedures, and generalize other classical well-studied stochastic models, eg. Branching Processes and Stochastic Context-free Grammars, that have been used in a variety of areas. Recursive Markov Decision Processes and Stochastic Games similarly extend ordinary finite decision processes and games, and they are natural models for recursive systems involving both probabilistic and nonprobabilistic (controlled) actions. In a series of recent papers with Kousha Etessami (U. of Edinburgh), we have introduced these models and studied central algorithmic problems regarding questions of termination, reachability, and analysis of the properties of their executions. In this talk we will present some of the basic theory and algorithms.

This is a Past Event

Event Type

**Scientific, Seminar**

Date

**April 24, 2007**

Time

2:00am
- 3:00am

Location

Simon Fraser University