Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 05 avril 2011 à 14h00 en B311, Cyril Nicaud nous parlera de : Mots de Lyndon aléatoires

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 : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr