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
Entropy of timed languages
- Date
- Tuesday, March 22 2011 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Eugene Asarin (LIAFA, Université Paris Diderot - Paris VII)
For timed languages, we define measures of their size: volume for a fixed finite number of events, and entropy (growth rate) as asymptotic measure for an unbounded number of events. These measures can be used for comparison of languages, and the entropy can be viewed as information contents of a timed language. In case of languages of deterministic timed automata, we give exact formulas for volumes. Next we characterize the entropy, using methods of functional analysis, as a logarithm of the leading eigenvalue (spectral radius) of a positive integral operator. We devise several methods to compute the entropy: a symbolical one for so-called "1 1/2-clock" automata, and two numerical ones: one using techniques of functional analysis, another based on discretization.
(The talk is based on Concur'09, FORMATS'09, FSTTCS'10 articles with Aldric Degorre)