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.