Partenaires


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Structuration Scientifique > Informatique > Combinatoire > Projet thématique « Étude de structures de treillis »

Projet thématique « Étude de structures de treillis »

Le projet se scinde essentiellement en deux parties. La première partie consiste à continuer l’exploration des structures liées aux arbres binaires (étiquetés ou pas), l’étude de la concaténation non associative relativement à la théorie des langages, l’étude de la décidabilité de la théorie universelle de certaines classes de monoïdes commutatifs… Par exemple, on poursuivra l’étude de la distance de rotation entre deux arbres binaires quelconques. Rappelons que trouver un algorithme polynomial pour calculer la distance de rotation entre deux arbres binaires (le nombre minimum de rotations pour transformer un arbre en un autre) est à ce jour un problème ouvert. Des travaux récents (Luccio et al.) suggèrent que ce domaine de recherche a encore des perspectives très prometteuses. En effet, l’obtention de bornes efficaces permettraient à terme d’estimer finement la distance entre deux arbres quelconques. Une approche nouvelle est alors de déterminer la distance exacte entre deux arbres situés dans des classes restreintes.

La seconde partie consiste à élargir les domaines de recherche actuels en explorant systématiquement les classes d’objets énumérées par les nombres de Motzkin ou Schröder d’un point de vue analogue à celui des arbres binaires.

Chercheurs et enseignants-chercheurs permanents :


LE2I - Laboratoire Electronique, Informatique et Image | webmestre : Antoine Trapet | info légales | logo SPIP 2