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 Stéphane Le Roux and Matthias Fuegger.

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

Séminaires passés

The theory of regular cost functions, from finite words to infinite trees.

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

 Denis Kuperberg
Le mardi 19 mars 2013 à 11:00
Salle de Conférence (Pavillon des Jardins)
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.

À propos du LSV

Agenda des séminaires

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

mar. 19 février

Les séminaires précédents