M2 Internship

Information per time unit in timed systems

Supervisors: Eugene Asarin and Aldric Degorre.

Timed words represent sequences of discrete events and continuous time durations, for example

a 1.234 b 3.141 a 2.71828 a 0.0001 b,

sets of such words (timed languages) are recognized by timed automata.  These concepts are studied since 1990s, they are extensively applied to modelling and verification of real-time systems.

Recently, we have explored the quantity of information (entropy) for timed words belonging to a timed language. This notion is theoretically appealing, and allows analysing compression and transmission of timed data. In fact entropy represents the quantity of information in bits/event in the timed words.

However, it would be very natural to consider timed words with respect to continuous time (instead of the number of events), and, in particular, to measure information in bits/second. This constitutes the aim of intrernship.

Some of the following questions will be addressed:

• how to associate a continuous-time dynamical system with a timed language?
• what are its natural entropy measures?
• how to compute the entropy  w.r.t. time given a timed automaton?
• how  Kolmogorov complexity of timed words depends on their duration?
• what is the meaning af all the previous for information channels?

The ideal candidate should know basics of timed automata/languages (e.g. course 2-8-2 of MPRI), some knowledge in symbolic dynamics, Kolmogorov complexity, functional analysis,  would be welcome (but not necessary).