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

Asymptotic behaviour of max-plus and min-plus automata

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

 Laure Daviaud
Date
Le mardi 13 mai 2014 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Laure Daviaud (LIAFA, Université Paris Diderot)

Min-plus and max-plus automata are non deterministic finite automata with weights (non-negative integers) on transitions. These automata compute functions from the set of words to the set of non negative integers including an infinite value.

Questions such as equivalence or comparison are undecidable problems. This implies the impossibility to precisely describe the evolution of these functions.

In this talk, I will give results about the description of the asymptotic behaviour of these functions. More precisely, given a function f computed by a min-plus (resp. max-plus) automaton, we consider a function from the set of positive integers defined by g:n -> max{f(w) | |w| < n} (resp. g:n -> min{f(w) | |w|>n}. I will present two results about the description of g. First, the asymptotic behaviour of g is of the form n^a where a is a rationnal from [0,1]. Second, it is possible to approximate the ratio g(n)/n.

These questions are related with the approximation of sets of matrices over the tropical (resp. max-plus) semiring.

This talk is based on joint works with Thomas Colcombet and Florian Zuleger.


À 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