Résumé : Dans cette présentation, on s'intéressera à deux sujets a priori distincts. Le premier concerne la génération aléatoire d'arbres planaires dans lequel on maîtrise le nombre d'occurrences d'un motif d'arbre. Le but est, partant d'un motif donné, de produire automatiquement une grammaire d'arbre dans laquelle les occurrences du motif sont marqués. Cette grammaire permet directement d'obtenir un générateur aléatoire en utilisant la méthode récursive, mais permet également d'obtenir une série génératrice bivariée. Le second est une présentation d'une famille de grammaires d'arbres et des automates qui y sont associés, appelés machines de Lukasiewicz. Cette famille fut utilisé pour résoudre le premier problème. Il s'agit d'une généralisation des grammaires d'arbre régulières. Si ces grammaires et les machines associés ont des propriétés de clôtures décevantes, on a pu décrire un algorithme de minimisation pour les machines déterministes.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |