Nicolas Basset (Université Libre de Belgique)

Il est en général impossible d’énumérer exhaustivement les mots d’une taille fixée « n » d’un automate fini car leur nombre croit exponentiellement par rapport à n. Par contre, il est bien connu comment avoir accès en temps polynomial à un mot typique de longueur n , c’est à dire qu’on peut simuler la mesure de probabilité qui donne la même chance à chaque mot de longueur n d’être tiré au sort. Cette mesure uniforme est celle d’entropie maximale au sens de Shannon. Pour les mots de longueur infini (et sous hypothèse de forte connexité de l’automate), la mesure d’entropie maximale décrite par Shannon (et connue sous le nom de mesure de Parry) peut se calculer en temps polynomial par rapport à la taille de l’automate.

Nous considérons les familles d’automates synchronisés sur les lettres communes et entrelacés sinon, qui sont un formalisme élégant et très utile pour modéliser les systèmes concurrents. Pour de tels modèles, il est indispensable d’adopter des méthodes compositionnelles qui combinent des calculs effectués sur les automates composants la famille sans jamais construire l’automate produit de taille prohibitive (exponentielle en le nombre d’automates composants la famille). Nous présentons des méthodes compositionnelles de calcul de mesures d’entropie maximale pour les mots finis (mesure uniforme) ou infinis (mesure de Parry). Nous proposons aussi des méthodes compositionnelles pour les mesures de Boltzmann. Les générateurs aléatoires associés à ces mesures ont été très étudiés récemment du fait de leur capacité à générer aléatoirement et de manière très efficace des objets combinatoires de grande taille.