M2 Internship

Information per time unit in timed systems

Supervisors: Eugene Asarin and Aldric Degorre.

Location: IRIF (Paris)

Context: ANR project MAVERIQ on a related theme starts in March 2021, PhD thesis available.

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.

In practice, it would be more relevant to consider timed words with respect to continuous time (instead of the number of events), and, in particular, to measure information in bits/second (bandwidth). This constitutes the aim of this internship.

Some of the following questions will be addressed:

define entropy (information production) per time unit for timed languages
relate information production to the structure of timed automata
develop an algorithm for numeric computation of the entropy
apply the notion of entropy per time unit to information encoding and transmission.

Depending on the work progress and the profile of the intern, the research will be theoretical or include an implementation in prototype software,

Basic knowledge of automata, languages, algorithmics, linear algebra, and taste for fundamental informatics are mandatory. The ideal candidate should know basics of timed automata/languages (e.g. course 2-8-2 of MPRI), also knowledge in symbolic dynamics/coding (e.g. 2-20-2) or information theory would be welcome (but not necessary).