Séminaire INFRES TELECOM ParisTech
Organisateurs:Hugues Randriam &Dario Rossi
Orateur: Jacques Sakarovitch (CNRS &Télécom ParisTech)
“A propos des automates avec multiplicité,sur les langages rationnels de même fonction génératrice”
Résumé: La plupart des modèles de calculs qu’ils soient dérivés de la machine de Turing (automates finis,à pile,à compteurs,etc.) ou non (systèmes de réécriture,réseaux de Petri,etc.) ont pour objet de distinguer parmi les séquences de symboles,suites d’actions,etc. celles qui sont acceptées,ou correctes,ou valides,de celles qui ne le sont pas. Les automates avec multiplicité (weighted automata en anglais) permettent d’associer à chaque séquence un coefficient,élément de l’univers qu’on aura choisi pour modéliser le phénomène étudié,et qui donne plus d’informations sur la séquence qu’un simple 0-1. Cela ouvre le champ à l’étude de systèmes quantitatifs.
Les possibilités de modélisation sont multipliées à l’infini,mais l’étude de ces automates avec multiplicité est naturellement plus complexe. Ces dernières années,j’ai développé avec mes étudiants des techniques dites structurelles qui permettent d’analyser au delà d’un résultat les calculs qui mènent à ce résultat. Dans cet exposé,j’en présenterai un aperçu avec la preuve du résultat suivant:
Si deux langages rationnels (ie acceptés par un automate fini) $L$ et $K$ ont la même fonction génératrice,c’est-à-dire que pour chaque entier $n$ il y a le même nombre de mots de longueur $n$ dans $L$ et dans $K$,il existe un transducteur fini lettre-à-lettre (un automate fini dont toutes les transitions sont étiquetées par un couple de lettres) qui réalise une bijection entre $L$ et $K$.
Cet énoncé,qui résout une conjecture obscure de la théorie confidentielle des structures automatiques,est une conséquence d’un raffinement de la décidabilité de l’équivalence de deux automates finis avec multiplicité dans $N$ —et en l’occurrence le prétexte à sa présentation:deux $N$-automates sont équivalents si,et seulement si,ils sont conjugués,par des matrices à coefficients dans $N$,à un même troisième et de l’interprétation de la conjugaison comme une succession de revêtements et de co-revêtements réalisés par fusion et éclatement des états.
Tout ceci est tiré d’un travail en collaboration avec Marie-Pierre Béal et Sylvain Lombardy,de l’université Paris-Est,Marne-la-Vallée.
Rossi
