On the Complexity of Computing Probabilistic Bisimilarity
| Dates: | 22 February 2012 |
|---|
| Times: | 14:00 - 15:30 |
|---|
| What is it: | Seminar |
|---|
|
|
Speaker: Professor Franck van Breugel. York University Toronto
Host: Richard Banach
Probabilistic bisimilarity is a fundamental notion of equivalence on labelled Markov chains. It has a natural generalisation to a probabilistic bisimilarity pseudometric, whose definition involves the Kantorovich metric on probability distributions. The probabilistic bisimilarity pseudometric has discounted and undiscounted variants, according to whether one discounts the future in observing discrepancies between states.
In his talk, we will look at the complexity of computing probabilistic bisimilarity and the probabilistic bisimilarity pseudometric on labelled Markov chains. We show that the problem of computing probabilistic bisimilarity is P-hard by reduction from the monotone circuit value problem. We also show that the discounted probabilistic bisimilarity pseudometric is rational and can be computed exactly in polynomial time using the network simplex algorithm and the continued fraction algorithm. In the undiscounted case we show that the probabilistic bisimilarity pseudometric is again rational and can be computed exactly in polynomial time using the ellipsoid algorithm.
This talk is based on joint work with Di Chen and James Worrell.
Travel and Contact Information
Find event
Lecture Theatre 1.4
Kilburn Building
Manchester
