BEGIN:VCALENDAR
PRODID:-//Columba Systems Ltd//NONSGML CPNG/SpringViewer/ICal Output/3.3-
 M3//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VEVENT
DTSTAMP:20120217T151325Z
DTSTART:20120222T140000Z
DTEND:20120222T153000Z
SUMMARY:On the Complexity of Computing Probabilistic Bisimilarity
UID:{http://www.columbasystems.com/customers/uom/gpp/eventid/}m4c-gyrcz3q
 d-iwk73b
DESCRIPTION:Speaker: Professor Franck van Breugel. York University Toront
 o\n\nHost: Richard Banach\n\nProbabilistic bisimilarity is a fundamental
  notion of equivalence on labelled Markov chains.  It has a natural gene
 ralisation to a probabilistic bisimilarity pseudometric\, whose definiti
 on involves the Kantorovich metric on probability distributions.  The pr
 obabilistic bisimilarity pseudometric has discounted and undiscounted va
 riants\, according to whether one discounts the future in observing disc
 repancies between states.\n\nIn his talk\, we will look at the complexit
 y of computing probabilistic bisimilarity and the probabilistic bisimila
 rity pseudometric on labelled Markov chains.  We show that the problem o
 f computing probabilistic bisimilarity is P-hard by reduction from the m
 onotone circuit value problem.  We also show that the discounted probabi
 listic bisimilarity pseudometric is rational and can be computed exactly
  in polynomial time using the network simplex algorithm and the continue
 d fraction algorithm.  In the undiscounted case we show that the probabi
 listic bisimilarity pseudometric is again rational and can be computed e
 xactly in polynomial time using the ellipsoid algorithm.\n\nThis talk is
  based on joint work with Di Chen and James Worrell.\n\n
STATUS:TENTATIVE
TRANSP:TRANSPARENT
CLASS:PUBLIC
LOCATION:Lecture Theatre 1.4\, Kilburn Building\, Manchester
END:VEVENT
END:VCALENDAR