Cyril Nicaud (LIGM, Paris Est)

Il y a 50 ans, Cerny a posé une conjecture combinatoire sur les automates, qui n’est toujours pas résolue. Un automate est dit synchronisé quand il existe un mot u et un état p tel que depuis n’importe quel état, si on lit u on arrive en p. Sa conjecture est que si l’automate synchronisé possède n états, alors il existe un tel u de longueur au plus ( n -1)2. Dans cet exposé, nous nous intéresserons à la version probabiliste de la conjecture de Cerny : on montrera qu’un automate aléatoire est non seulement synchronisé (résultat déjà prouvé par Berlinkov), mais qu’en plus la conjecture de Cerny est vraie avec forte probabilité.