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 Laurent Doyen and Stefan Göller.

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

Prochain séminaire

Querying regular languages over sliding-windows

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

 Markus Lohrey
Date
Le mardi 24 juillet 2018 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Markus Lohrey (University of Siegen)

Sliding-window streaming algorithms get as input a stream of data values and have to answer queries about the last n values for a certain window size n. In the talk we consider queries that are given by regular languages. More precisely, we consider the so-called sliding window word problem for a language 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 belongs to L. We are mainly interested in the space complexity of this problem measured in the window length n. For regular languages, we prove that the space complexity of the sliding window word problem is either constant, logarithmic, or linear. Moreover, for the constant and logarithmic space classes we provide very natural characterizations: For every regular language L the sliding window word problem can be solved in (i) constant space if and only if L is a boolean combination of regular length languages and suffix-testable languages 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 with a two-sided error, then the above space trichotomy becomes a space quatrochotomy: for every regular languages, the space complexity of the sliding window word problem is either constant, doubly logarithmic, logarithmic, or linear.


Séminaires à venir

À propos du LSV

Agenda des séminaires

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

mar. 24 juillet

Les séminaires précédents