Automates à groupe aléatoires

Les automates à groupes sont des automates déterministes et complets tels que chaque lettre est une bijection de l'ensemble des états dans lui-même. L'étude combinatoire de tels objets est donc par nature très liée à celle des permutations. L'analyse en moyenne de la minimalité des automates à groupes permet d'améliorer (en moyenne) les algorithmes connus, passant de $n\log n$ à un temps linéaire. Cette étude permet également de tirer au sort, en temps moyen linéaire, des automates à groupe avec $n$ états. Au passage on établira que la probabilité qu'une permutation ait au moins deux cycles de taille maximale est équivalente à $e^\gamma/2n$ où $\gamma$ est la constante d'Euler (résultat obtenu à l'aide de Philippe Flajolet avec des méthodes développées par Xavier Gourdon).