Processus stochastiques d’entropie maximale pour les automates temporisés

Nous rappelons d’abord la question que nous généraliserons par la suite au cas temporisé : Comment générer aléatoirement et de façon quasi uniforme les chemins dans un graphe? Une solution à cette question est fondée sur le processus stochastique d’entropie maximale décrit par Shannon (et connu sous le nom de mesure de Parry en dynamique symbolique et théorie ergodique). Ensuite, nous généralisons les notions de processus stochastique et d’entropie aux automates temporisés.

Nous construisons, à l’instar du cas non temporisé, un processus stochastique d’entropie maximale pour un automate temporisé, défini à l’aide des attributs spectraux (rayon spectral, fonctions propres) de l’opérateur d’Asarin et Degorre, qui est un analogue temporisé de la matrice d’adjacence d’un graphe. Ce processus permet de faire une génération aléatoire quasi-uniforme des calculs d’un automate temporisé.

En application, nous décrivons la génération aléatoire (quasi-)uniforme de permutations dont les mots (formés par les montées et descentes successives) appartiennent à un langage régulier.