# LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue).
If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

## Past Seminars

### Querying regular languages over sliding-windows

- Date
- Tuesday, July 24 2018 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- 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.