Pablo Rotondo

(LIGM, Université Gustave Eiffel)

Cet exposé porte sur la simplification d'expressions aléatoires représentées par des arbres d'opérateurs. Pour les arbres uniformes, nous avons démontré que la présence d'un opérateur dit absorbant entraîne une simplification très forte : la taille attendue de l'expression réduite reste bornée, quel que soit le nombre de nœuds de départ, ce qui montre une forte manque d'expressivité de ce modèle. Cet effet résiste même à certaines constructions plus complexes visant à éviter les redondances.

Nous considérons ensuite des arbres aléatoires de type BST, rapides à générer et paramétrables, et nous étudions l'effet d'une réduction induite par un opérateur absorbant. Nous démontrons l'existence de deux seuils donnant lieu à cinq régimes, allant d'une réduction quasi nulle à une réduction presque totale. Contrairement aux arbres uniformes, les arbres BST-like pourraient ainsi permettre de produire des expressions aléatoires plus variées et pertinentes.

Cet exposé est basé sur des travaux en collaboration avec Florent Koechlin, Cyril Nicaud et Carine Pivoteau.