Abstract: Probabilistic automata are finite state machines that roll dice in each step to decide the next state on reading an input symbol. Such machines were first introduced by Rabin in the 1960s as a computational model on finite words, and, more recently, the theory has been extended to consider infinite length inputs. This talk will survey results about such machines, contrasting it with the theory of regular languages, and discuss open problems and applications to model checking.
Results presented will include joint work with Rohit Chadha, Dileep Kini, and Prasad Sistla.
Bio: Mahesh Viswanathan obtained his bachelor's degree in computer science from the Indian Institute of Technology at Kanpur, and his doctorate from the University of Pennsylvania. He was a post-doctoral fellow at DIMACS with a joint appointment with Telcordia Technologies in 2000-01. Since 2001, he has been on the faculty at the University of Illinois at Urbana-Champaign. His research interests are in the core areas of logic, automata theory, and algorithm design, with applications to the algorithmic verification of cyberphysical and stochastic systems.