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:
Querying regular languages over sliding-windows
STATUS:CONFIRMED
ATTENDEE;CN="Markus Lohrey
":
MAILTO:no@spam.com
DESCRIPTION:
Sliding-window streaming algorithms get as input a stream of
data values and have to answer queries about the last n val
ues for a certain window size n. In the talk we consider que
ries that are given by regular languages. More precisely\, w
e consider the so-called sliding window word problem for a l
anguage L: Given a data stream of symbols a_1 a_2 a_3 ...\,
answer at every time instant t\, whether a_{t-n+1} ... a_t b
elongs to L. We are mainly interested in the space complexit
y of this problem measured in the window length n. For regul
ar languages\, we prove that the space complexity of the sli
ding window word problem is either constant\, logarithmic\,
or linear. Moreover\, for the constant and logarithmic space
classes we provide very natural characterizations: For ever
y regular language L the sliding window word problem can be
solved in (i) constant space if and only if L is a boolean c
ombination of regular length languages and suffix-testable l
anguages and in (ii) logarithmic space if and only if L is a
boolean combination of regular length languages and regular
left ideals. If we allow randomized streaming algorithms wi
th a two-sided error\, then the above space trichotomy becom
es a space quatrochotomy: for every regular languages\, the
space complexity of the sliding window word problem is eithe
r constant\, doubly logarithmic\, logarithmic\, or linear.
DTSTART;TZID=Europe/Paris:20180724T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=201807241
100
UID:LSVsemLSV.201807241100@lsv.ens-cachan.fr
LOCATION:Salle de ConfĂ©rence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR