LFCS Seminar: Eugene Asarin
Volume and entropy of regular timed languages
What 


When 
May 13, 2013 from 04:00 PM to 05:00 PM 
Where  IF 2.33 
Contact Name  jcheney@inf.ed.ac.uk 
Add event to calendar 
vCal iCal 
(based on joint work with A. Degorre, N. Basset, D. Perrin, M.P. Béal)
In the beginning of my talk I will recall two kinds of notions and results:
1. Timed languages and automata, introduced in early 90s are extensively studied and applied for modelling and verification of realtime systems.
2. Notion of entropy of a language (as measure of its size or information contained in its words) and a classical recipe for computing the entropy of a regular language.
In the main part of the talk I will combine these two ingredients to come up with the notion of entropy of timed languages.
More precisely, in this work, 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.
If the time permits, I will explain how these results apply to the transmission of hybrid discrete/analog information.