Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Eugene Asarin

LFCS Seminar: Eugene Asarin

— filed under:

Volume and entropy of regular timed languages

  • LFCS Seminar
When May 13, 2013
from 04:00 PM to 05:00 PM
Where IF 2.33
Contact Name
Add event to calendar vCal

 (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 real-time 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.

Document Actions