Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire ALGO

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Prochain séminaire: Mardi 19 Novembre 2019
Florent Koechlin (LIGM, Paris-Est Marne la Vallée), Pablo Rotondo (LITIS, Rouen)
Les expressions aléatoires uniformes manquent d'expressivité

Résumé

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.

Autres séminaires prévus (le programme n'est qu'indicatif):
GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr