Résumé : Dans cet exposé je présenterai diverses propriétés combinatoires et algorithmiques des mots de Lyndon aléatoires. Je parlerai principalement de factorisation standard (travail avec F. Bassino et J. Clément) et de décomposition en mots de Lyndon. On verra des techniques analytiques et des techniques probabilistes pour aborder ce genre de questions. Le résultat principal est que l'on peut décomposer en mots de Lyndon en temps moyen sous-linéaire. On utilise pour cela une bonne compréhension de ce qu'est un mot aléatoire "typique" et des techniques d'algorithmique du texte.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr