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