Réductions d’arbres d’expressions en présence d’un élément absorbant

Réductions d’arbres d’expressions en présence d’un élément absorbant

Redondance des expressions, élément absorbant

On fait généralement la distinction entre la syntaxe d’une expression, c’est-à dire l’arbre étiqueté, et sa sémantique, c’est-à-dire l’objet qu’il représente. Pour de nombreusesclasses d’expressions syntaxiques, on peut voir apparaître un phénomène de redondance : plusieurs expressions di￿érentes représentent les mêmes objets. Par exemple : — les expressions régulières (a + b)⇤, (a + b)⇤ +(bab)⇤ et (a + b)(a + b)⇤ +  » représentent le même langage, celui de tous les mots sur l’alphabet {a,b}

— les formules logique >, >_x, et ¬? représentent la même fonction booléenne, la tautologie vraie. — les expressions arithmétiques x/2 et 4 ⇥ (x/8) sont équivalentes. Il apparaît ainsi immédiat que tirer au hasard une expression n’est pas du tout équi valent à tirer au hasard l’objet qu’elle représente; certains objets sont sur-représentés par rapport à d’autres, selon le nombre d’expressions d’une taille donnée qui les décrivent.

Dans ce cas, les analyses en moyennes et les benchmarks utilisant des expressions aléatoires sont-ils pertinents? Nous allons voir dans cette partie de la thèse que la réponse à cette question est souvent négative. Dans cette partie de la thèse, nous nous sommes restreints à la prise en compte d’une redondance très simple sur les arbres d’expressions, due à la présence d’un élément absorbant.

Un arbre P est dit absorbant pour un opérateur ~ si toute ex pression de la forme ~ /\ P T ou ~ /\ T P , avec T une expression quelconque, est équivalente sémantiquement à P (c’est-à-dire qu’elle représente le même objet que P). Dans tous les exemples mentionnés précédemment on trouve des éléments absor bants : — l’expression (a+b)⇤ est absorbante pour l’union + pour les expressions régulières sur les lettres a et b. En e￿et,

l’union d’un langage quelconque avec tous les mots possibles donne encore le langage de tous les mots. Ce n’est d’ailleurs pas le  seul élément absorbant pour l’union, il y a aussi (a⇤ + b)⇤, (a⇤b⇤)⇤, ((a + « )b)⇤,  » +(a+b)(a+b)⇤, … — >estabsorbant pour l’opérateur _. En e￿et, vrai ou n’importe quelle expression est toujours vrai. Demême?estabsorbantpour^.Ettouteexpressionéquivalente à ?(comme x^¬x)est absorbante pour ^.

On se convainc facilement que le cadre de travail du chapitre 2 permet aussi d’étudier les éléments ab sorbants à droite. Pour les autres chapitres, il faut véri￿er plus en détail les calculs, même si les résultats ne devraient a priori pas changer. — PourLTL, >est aussi absorbant pour l’opérateur _, et ? est absorbant pour ^.

Si nous voulons utiliser la sémantique propre de LTL, nous pouvons dire que ?est absorbant à droite pour U : U?estéquivalent à ?, mais nous sortons légèrement du cadre que nous avons étudié dans cette thèse, car l’élément n’est absorbant que d’un côté. — 0(et x x, ln(1), …) est absorbant pour la multiplication ⇥.

Le but principal de cette partie sur les arbres d’expressions est de montrer que la seule présence d’un élément absorbant pour un opérateur ￿xé, dans la sémantique des arbres d’expressions, su￿t en général à montrer que la distribution uniforme est dégénérée par rapport aux objets représentés. Par conséquent cette distribution ne devrait pas être utilisée pour l’étude en moyenne des algorithmes– qui étudient ￿nalement plus la dégénérescence de la distribution uniforme que le comportement des algorithmes–nipourlagénérationaléatoire pourlesbenchmarks.

Ce phénomène est su￿samment général pour nous permettre d’exhiber un grand nombre de classes d’expressions qui rentrent dans ce cadre, tout en évitant d’avoir à adapter les preuves au cas par cas, selon la sémantique particulière de chacune des expressions étudiées. Nous clôturons cette partie en étudiant la distribution ABR, et en montrant no tamment que l’in￿uence d’un élément absorbant sur cette distribution est a priori plus complexe que pour la distribution uniforme