Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Entropie et quantité d’information dans les modèles des systèmes computationnels – EQINOCS

EQINOCS : Entropie et Quantité d’INformation dans les mOdèles des systèmes ComputationnelS

Ce projet est centré sur l'analyse de l'entropie dans les modèles computationnels, en particulier ceux issus de la vérification. L'objectif est d'y adapter et d'y appliquer la notion d'entropie.

Enjeux et objectifs

1.contribuer significativement à la théorie relative à l'entropie (ou l'entropie généralisée) de systèmes dynamiques associés à des transducteurs, des arbres, des jeux et des automates cellulaires et temporisés. <br />2.étudier les processus d'information dans les systèmes computationnels. Nous voulons mesurer la quantité d'information circulant dans ou générée par de tels systèmes. Outre un éclairage nouveau sur ceux-ci, cette étude fournirait de nouveaux outils pour mesurer leur niveau de sécurité et la qualité des protocoles de communication et suggèrerait une nouvelle approche de la compression de données. <br />3.identifier et explorer les applications à l'analyse et au model-checking quantitatifs des systèmes computationnels. Nous pensons que, par rapport aux approches probabilistes traditionnelles, les méthodes basées sur l'entropie ont deux avantages importants : elles ne nécessitent pas une connaissance exacte de tous les évènements du système et elles peuvent être beaucoup plus simples à mettre en œuvre.

Nous appliquerons les techniques de la théorie d'automates et celle de codes, de la théorie d'information et la complexité de Kolmogorov, de la dynamique symbolique et théorie ergodique, de la vérification, de l'analyse fonctionnelle des opérateurs linéaires positifs, de la combinatoire, de l'analyse numériques. Nous implémenterons et testerons les algorithmes développés sur des études des cas.

Résultat marquant : Dynamique symbolique temporisée et sa théorie spectrale
Les langages temporisés réguliers ont été représentés par des systèmes dynamiques de décalage. Un opérateur intégral linéaire positif sur un espace de Banach est naturellement associé à ce système. Cet opérateur contient l’information essentielle sur le langage : son rayon spectral caractérise l’entropie du langage, sa résolvante correspond à la fonction génératrice du langage. L’opérateur possède un trou spectral ce qui garantit la convergence des simples algorithmes numériques.

Fait marquant : un colloque co-organisé.
Ce colloque, qui apparait sur la page Web de l’AMS comme “PIMS/EQINOCS Workshop on Automata and Ergodic Theory” aura lieu à Vancouver en juin 2013 et mettra ensemble les mathématiciens et les informaticiens travaillant sur les thèmes proches à notre projet.

Nous attendons des nouveaux résultats sur l'entropie pour des nombreuses classes de systèmes computationnels et leurs applications théoriques et pratiques.

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,

Ce projet est centré sur l'analyse de l'entropie pour les modèles computationnels. L'objectif est d'adapter et d'appliquer la notion d'entropie aux modèles computationnels issus du domaine de la vérification. L'analyse permettra de progresser dans trois directions.

1: Nous souhaitons obtenir des contributions théoriques significatives concernant l'entropie (ou l'entropie généralisée) de systèmes dynamiques associés à des transducteurs, des arbres, des jeux et des automates cellulaires et temporisés.

2: Nous voulons aussi étudier les processus d'information dans les systèmes computationnels. Il est bien connu que les systèmes computationnels traitent et transmettent de l'information. Dans ce projet nous voulons mesurer la quantité d'information circulant dans ou génrérée par de tels systèmes. Ceci donnerait un éclairage nouveau aux systèmes computationnels, fournirait de nouveaux outils pour mesurer le niveau de sécurité des systèmes et la qualité des protocoles de communication, et donnerait une nouvelle approche pour la compression de données.

3:Nous identifierons et explorerons les applications à l'analyse quantitative et au model-checking quantitatif des systèmes computationnels. Nous pensons que, en comparaison avec les approches probabilistes traditionnelles, les méhodes basées sur l'entropie ont deux avantages importants : elles ne nécessitent pas une connaisance exacte de tous les évènements du système, et elles peuvent être beaucoup plus simples à implémenter.

Coordinateur du projet

Monsieur Eugene ASARIN (UNIVERSITE DE PARIS 7) – asarin@liafa.jussieu.fr

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

VERIMAG CNRS - DELEGATION REGIONALE RHONE-ALPES SECTEUR ALPES
LIAFA UNIVERSITE DE PARIS 7
LIGM UNIVERSITE PARIS-EST MARNE LA VALLEE
LACL UNIVERSITE PARIS-EST CRETEIL VAL DE MARNE

Aide de l'ANR 374 063 euros
Début et durée du projet scientifique : - 48 Mois

Liens utiles