Applications asynchrones à fenêtre glissante

Olivier CARTON
(Travail en collaboration avec Marie-Pierre Béal)

(Institut Gaspard-Monge, Marne-la-Vallée)

Résumé Nous introduisons une notion d'applications locales asynchrones qui peuvent être réalisées par des tranducteurs étiquetés par  . Nous montrons que sous certaines conditions, il possible de synchroniser ce transducteur par éclatement d'états pour obtenir un transducteur étiqueté par  , où k est un entier fixe. Dans le cas d'un transducteur avec un graphe fortement connexe, cette synchronisation peut être considérée comme une implémentation d'un algorithme de C. Frougny et J. Sakarovitch pour la synchronisation des relations rationnelles à délai borné. L'algorithme s'applique lorsque le transducteur a un taux de transmission entier et constant sur les cycles et que le graphe est fortement connexe. Il conserve la localité de l'automate d'entrée. Nous montrons que la taille de la fenêtre glissante de l'application locale croît de façon linéaire lors de la synchronisation mais que le nombre d'états peut par contre croître de façon exponentielle. Dans le cas d'un graphe non fortement connexe, l'algorithme de C. Frougny et J. Sakarovitch ne conserve plus la localité de l'automate d'entrée du transducteur. Nous donnons un autre algorithme qui résoud ce cas sans perdre les bonnes propriétés conservées par éclatement d'états.