Nicolas Gast (Laboratoire d'Informatique de Grenoble)

Les mots de Sturm sont des mots infinis qui admettent plusieurs définitions équivalentes: ce sont les mots de complexité minimale, ce sont les mots équilibrés apériodiques et ce sont les mots mécaniques. De plus ces mots ont d’étonnantes propriétés d’optimalité qui peuvent être appliquées aux réseaux.

Une manière naturelle de les généraliser aux arbres est d’étendre la notion de complexité. Ce faisant, on perd les bonnes propriétés des deux autres définitions équivalentes. Une autre manière de généraliser aux arbres binaires infinis est de considérer les arbres non-ordonnés où l’on obtient des résultat intéressants.

À travers cet exposé, nous nous intéresserons à la notion d’arbre où les fils ne sont pas ordonnés infini et tenterons de répondre à diverses questions: qu’est-ce qu’un arbre régulier? Comment définir la densité? Comment définir et caractériser les arbres balancés et mécaniques?