University of Antwerp, Belgium
10:30 am, May 7, 2010
Room G.03, Informatics Forum
In this talk we introduce a number of well-studied classes of structured Markov chains of infinite size that are often used in the areas of queueing theory, communication networks, etc. They include Quasi-Birth-Death Markov chains, M/G/1-type and GI/M/1-type Markov chains, tree-structured Markov chains and more. The focus of this talk will be on the development and implementation of fast algorithms to compute a number of fundamental matrices that form the key step in determining of the steady state vector of these Markov chains. Some links with 1-counter automata, recursive Markov chains, probabilistic push down systems and branching processes are also discussed.