Entropy and quantity of information in models of computational systems – EQINOCS

We will apply techniques of automata an code theory, information theory and Kolmogorov complexity, symbolic dynamics and ergodic theory, verification, functional analysis of positive linear operators, combinatorics and numerical analysis. We will implement the algorithms developed and test them on case studies.

A significant result: Symbolic timed dynamics and spectral theory
Timed languages are represented as shift dynamical systems. A positif integral linear operator on a Banach space ais naturally associated to this system. This operator contains essential information on the language: its spectral radius characterizes the entropy, its resolvent corresponds to the generating function of the language .

A significant fact: co-organized workshop
This event, quoted on the AMS web page as “PIMS/EQINOCS Workshop on Automata and Ergodic Theory« will ake place at Vancouver in June 2013 and bring together mathematicians s and computer scientists working on themes close to our project.

We are awaiting new results on entropy of computational systems and their theoretical and practical applications

1.Asarin E., Basset N., Degorre A., Perrin D. Generating functions of timed languages. - MFCS’2012 :124-135
2.E. Asarin, N. Basset, M.-P. Béal, A. Degorre, D. Perrin: Toward a Timed Theory of Channel Coding. FORMATS 2012: 27-42
3.R. Bozianu, C. Dima,C. Enea. Model-checking an Epistemic ?-calculus with Synchronous and Perfect Recall Semantics TARK 2013
4.Asarin E., Basset N., Degorre A., Spectral gap in timed automata. Submitted to FORMATS 2013
5.L. Bienvenu, B. Monin. von Neumann's biased coin revisited. LICS 2012 :145-154
6.J. Cervelle: Covering Space in the Besicovitch Topology. LATA 2012: 169-178
7.D. P. Guelev, C. Dima: Epistemic ATL with Perfect Recall, Past and Strategy Contexts. CLIMA (Computational Logic in Multi-Agent Systems) 2012: 77-93
8.N. Basset: A maximal entropy stochastic process for a timed automaton. ICALP 2013
9.Slissenko, A., Towards analysis of information structure of computations, International Conf. Philosophy, Mathematics, Linguistics: Aspects of Interaction (PhML'2012), Saint Petersburg, Russia, 2012, 182—192
10.J.-F. Kempf, M. Bozga, O. Maler: As Soon as Probable: Optimal Scheduling under Stochastic Uncertainty. TACAS 2013: 385-400
11.A. Donzé, T. Ferrère, Oded Maler, Efficient Robust Monitoring for STL. CAV 2013
12.N. Basset : Counting and generating permutations using timed languages. Submitted to MFCS 2013
13. N. Aubrun and M.-P. Béal,Tree algebra of sofic tree languages, submitted

This project is centered on entropy analysis of models of computational systems. The goal is to adapt and apply the notion of entropy to models of computational systems (based on the concept of automata). This analysis will lead to progress in three directions.

1:We aim to obtain important theoretical contributions concerning entropy of (generalized) dynamical systems associated to trees, transducers, games, cellular and timed automata.

2:We wish to study information processes in computational systems. It is a commonplace that computational systems process and transmit information. In this project we will measure the quantity of information circulating/or generated by such systems. This would shed new light on computational systems, and provide new tools to assess computer security and performance of communication protocols, and new approaches to data compression.

3: We will identify and explore applications to quantitative analysis and quantitative model-checking of computational systems. We believe that, compared to more usual probability-based approaches, entropy methods have two important advantages: they do not require exact knowledge of probabilities of all the events in the system, and they can be much easier to implement.