Florent Koechlin (LIGM, Paris-Est Marne la Vallée)

Dans cet exposé, nous nous interrogeons sur la pertinence de modèles aléatoires uniformes pour analyser des algorithmes qui prennent en entrée des expressions. Dans un premier temps, nous introduisons un cadre général pour décrire ce que nous entendons par expressions, et nous nous plaçons dans le cas où il y a un motif absorbant pour un opérateur donné, qui permet de simplifier les expressions tout en préservant leur sémantique. Nous prouvons alors qu’en simplifiant au maximum une expression aléatoire uniforme de taille n, nous obtenons une expression équivalente de taille constante en moyenne. Cela prouve que les expressions aléatoires uniformes manquent d’expressivité, dès qu’il y a un motif absorbant. Par exemple, (a+b)* est absorbant pour l’union pour les expressions régulières sur {a,b}, donc les expressions régulières aléatoires peuvent être considérablement réduites en utilisant la simplification induite.

Travail en commun avec Cyril Nicaud.