# 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

### Effectively regular downward closures

- Date
- Tuesday, October 28 2014 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Georg Zetzsche (TU Kaiserslautern)

The downward closure of a language is the set of all (not
necessarily contiguous) subwords of its members. It is a
well-known consequence of Higman's Lemma that the downward
closure of every language is regular.

Aside from encoding interesting counting properties, the
downward closure constitutes a promising abstraction: If L
is the set of action sequences of a system, then the
downward closure of L is precisely what is observed through
a lossy channel, i.e. when actions can go unnoticed
arbitrarily. Hence, if the downward closure is available as
a regular language, the equivalence and even inclusion of
system behaviors can be decided with respect to such
observations.

However, there are only few classes of languages for which
it is known how to compute the downward closure of a given
language as a finite automaton. This talk presents new
approaches to this problem.