Login
Talks & Seminars
Title: Approximate Verification of the Symbolic Dynamics of Markov Chains
Dr. Akshay Sundararaman, IRISA, France
Date & Time: September 28, 2012 15:45
Venue: Lecture Hall, 03rd Floor, Dept. of Computer Science & Engg., Kanwal Rekhi Building
Abstract:
A finite state Markov chain M is often viewed as a probabilistic transition system. An alternative view is to regard M as a linear transform operating on the space of probability distributions over its set of nodes {1, . . . , n}. We are then interested in the sequences of probability distributions obtained by repeatedly applying M to an initial set of distributions. The novel idea here is to discretize the probability value space [0,1] into a finite set of intervals. Then each probability distribution; is associated with a discretized distribution d, which is the unique n-tuple of intervals such that; (i) belongs to d(i) for all i. Now, considering the set of discretized distributions as a finite alphabet, each sequence of probability distributions generates an infinite string over this finite alphabet. Thus, given an initial set of distributions, the symbolic dynamics of M consists of a language of infinite strings over the finite alphabet of discretized distributions. We investigate whether the symbolic dynamics meets a specification given as a linear time temporal logic formula, whose atomic propositions assert that the current probability of a node falls in some interval. We come up with exact and approximate approaches to tackle this problem. The motivation for considering this symbolic dynamics is to avoid the complications and complexity caused by numerically tracking sequences of probability distributions exactly. In applications, such as those arising from biochemical networks, exact estimates of the distributions are neither feasible nor important and using the symbolic dynamics could provide significant benefits. -- This is joint work with M. Agrawal, B. Genest and P. S. Thiagarajan.
Speaker Profile:
More details about Dr. Akshay Sundararaman is available at http://people.irisa.fr/akshay/.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback