BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:
On decision problems for Probabilistic Büchi Automata
STATUS:CONFIRMED
ATTENDEE;CN="Nathalie Bertrand
":
MAILTO:no@spam.com
DESCRIPTION:
Probabilistic Büchi automata (PBA) are finite-state accepto
rs for infinite words where all choices are resolved by fixe
d distributions and where the accepted language is defined b
y the requirement that the measure of the accepting runs is
positive. In this work we describe a complementation operato
r for PBA and a discuss on several algorithmic problems for
PBA. All interesting problems\, such as checking emptiness o
r equivalence for PBA or checking whether a finite transitio
n system satisfies a PBA-specification\, turn out to be unde
cidable. An important consequence of these results are sever
al undecidability results for stochastic games with incomple
te information\, modelled by partially-observable Markov dec
ision processes (POMDP) and w-regular winning objectives. Fu
rthermore\, we study an alternative semantics for PBA where
it is required that almost all runs for an accepted word are
accepting\, which turns out to be less powerful\, but has a
decidable emptiness problem. This is a joint work with Chri
stel Baier and Marcus Groesser.
DTSTART;TZID=Europe/Paris:20080205T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=200802051
100
UID:LSVsemLSV.200802051100@lsv.ens-cachan.fr
LOCATION:Salle de Conférence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR