Next: Langages reconnaissables Up: Home Page

Combinatoire des automates

Mes premiers travaux en théorie des automates concernaient un problème combinatoire toujours ouvert à ce jour. Considérons un automate (déterministe, complet) fini A. Chaque mot u du monoïde libre A^* induit alors une application de l'ensemble des états Q dans lui-même. Le rang de u (dans l'automate considéré) est par définition le cardinal de l'image de cette application. J'ai proposé la conjecture suivante, qui généralise une conjecture proposée par J. Cerny :

Si dans un automate à n états, il existe un mot de rang inférieur ou égal à k, alors il existe un tel mot de longueur inférieur ou égal à (n-k)².

J'ai montré que la borne k était optimale et que la conjecture était vraie pour k < 4 (le cas k = 3 est déjà très technique). J'ai également résolu la conjecture dans un certain nombre de cas particuliers et j'ai amélioré à plusieurs reprises les bornes supérieures connues [2, 4, 5, 6, 7, 8, 16]. Ces travaux successifs sont résumés dans ma thèse de troisième cycle. Enfin j'ai montré qu'on pouvait obtenir une borne supérieure en n³ moyennant un résultat de combinatoire sur les ensembles finis [27], résultat qui a été effectivement démontré par P. Frankl en 1982. A ce jour, la conjecture est toujours ouverte.

J'ai également résolu avec J.M. Champarnaud un problème portant sur le nombre d'états maximal que pouvait avoir l'automate minimal reconnaissant un ensemble de mots de longueur n donnée [57].