M2 Internship

Compression of mixed (discrete-continuous) signals

Supervisors: Eugene Asarin and Aldric Degorre.

A mixed signal contain discrete  and real-valued data. Discrete data corresoponds to events, the real-valued - to time or other physical measurments (temperature, speed)   for example

a, 1.234,  0.17, b 3.141 a 2.71828 a 0.0001 b.

We want to compress such data - exactly for discrete data and with some precision for continuous data. The aim of this internship is to develop novel compression methods based on our recent developments on entropy of timed languages.

After a study of  the state-of-art in approximate compression of mixed data, some of the following theoretical questions will be addressed:

• how to formalize  entropy lower bounds for approximate compression?
• how to compress timed words?
• how to deal with other kinds of continuous data?
• what is the meaning af all the previous for information channels?

the experimental part of the work could be as follows:

• find practically relevant sets of data words;
• formslize naïve compression algorithms and measure their performance;
• implement novel compression algorithms based on entropy of data and timed languages;
• compare performance of two kind of algorithms;
• explore posssible applications.

The ideal candidate should know basics of  timed automata/languages (e.g. course 2-8-2 of MPRI) and have good programming skills;  also some knowledge in information theory and/or functional analysis,  would be welcome (but not necessary).