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:
Quantitative Languages: Decision Problems\, Expressive Power
\, and Closure Properties
STATUS:CONFIRMED
ATTENDEE;CN="Laurent Doyen
":
MAILTO:no@spam.com
DESCRIPTION:
Quantitative generalizations of classical languages\, which
assign to each word a real number instead of a boolean value
\, have applications in modeling resource-constrained comput
ation. We use weighted automata (finite automata with transi
tion weights) to define several natural classes of quantitat
ive languages over finite and infinite words; in particular\
, the real value of an infinite run is computed as the maxim
um\, limsup\, liminf\, limit average\, or discounted sum of
the transition weights. We define the classical decision pro
blems of automata theory (emptiness\, universality\, languag
e inclusion\, and language equivalence) in the quantitative
setting and study their computational complexity. As the dec
idability of language inclusion remains open for some classe
s of weighted automata\, we introduce a notion of quantitati
ve simulation that is decidable and implies language inclusi
on. We also give a complete characterization of the expressi
ve power of the various classes of weighted automata. In par
ticular\, we show that most classes of weighted automata can
not be determinized. Finally\, for quantitative languages L\
, L'\, we study the operations max(L\,L')\, min(L\,L')\, and
1-L as natural generalizations of the boolean operations; w
e also consider the sum L + L'. We establish the closure pro
perties of all classes of quantitative languages with respec
t to these four operations. This talk is based on joint work
with Krishnendu Chatterjee and Tom Henzinger.
DTSTART;TZID=Europe/Paris:20081215T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=200812151
100
UID:LSVsemLSV.200812151100@lsv.ens-cachan.fr
LOCATION:Salle de ConfĂ©rence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR