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
The theory of regular cost functions, from finite words to infinite trees.
- Date
- Tuesday, March 19 2013 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Denis Kuperberg (LIAFA, Université Paris Diderot)
The theory of regular cost functions, initiated by Colcombet and following work with Mikołaj Bojańczyk, is a satisfying framework to extend a large spectrum of results on regular languages to a quantitative setting. I will present the theory, and give an overview of results obtained in my thesis. On finite and infinite words, we generalize a number of results from the theory of regular languages, often by showing equivalence between different formalisms (in terms of automata, logics, or semigroups). In particular we show that we can extend the notion of syntactic congruence to this quantitative framework. We also study the temporal class, which does not have a counterpart in language theory. On infinite trees, we show that the Rabin-Kupferman-Vardi theorem on languages is generalized in an unexpected way, and gives rise to the class of quasi-weak cost functions. The study of this class allows us to obtain a decidability result on infinite tree languages : it is decidable whether a Büchi language is weak.