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
Asymptotic behaviour of max-plus and min-plus automata
- Date
- Tuesday, May 13 2014 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- 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.