LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Equivalence of Labeled Markov Chains

Tuesday, December 18 2007 at 11:00AM
Salle de Conférence (Pavillon des Jardins)
Laurent Doyen (EPFL, Suisse)

We consider the equivalence problem for probabilistic machines. Two probabilistic machines are equivalent if every finite sequence of observations has the same probability of occurrence in the two machines. We show that deciding equivalence is polynomial for labeled Markov chains, using a reduction to the equivalence problem for probabilistic automata, which is known to be polynomial. We provide an alternative algorithm to solve the latter problem, which is based on a new definition of bisimulation for probabilistic machines.

Then, we consider the equivalence problem for labeled Markov decision processes (LMDPs) which asks given two LMDPs whether for every way of resolving the decisions in each of the processes, there exists a way of resolving the decisions in the other process such that the resulting probabilistic machines are equivalent. The decidability of this problem remains open. We show that the strategies used to resolve the decisions can be restricted to be observation-based, but may require infinite memory.

This is a joint work with Tom Henzinger and Jean-Francois Raskin.

About LSV