Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Equivalence of Labeled Markov Chains

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

Date
Le mardi 18 décembre 2007 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
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.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents