Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 26 Avril 2016

Fonction de récurrence des mots Sturmiens: une étude probabiliste

par Pablo Rotundo (IRIF, Paris et GREYC, Caen)

Nous nous intéressons aux mots infinis non périodiques qui ont deux principales propriétés: ils ont un petit nombre de facteurs finis (basse complexité), et ces facteurs re-apparaissent une infinité de fois à intervalles bornés (récurrence). L'exemple le plus simple et le plus classique est celui des mots Sturmiens et ses dérivés, qui a été très largement étudié.

Mais les mots de Sturm n'ont jamais été étudiés de façon probabiliste, et nous voulons répondre à la question suivante « à quoi ressemble un mot sturmien aléatoire? » Nous définissons un modèle probabiliste naturel pour cette question et nous nous concentrons sur l’étude de la fonction de récurrence qui décrit les intervalles de temps où re-apparait un facteur. Je présente les méthodes que nous avons utilisées, les résultats que nous avons déjà obtenus, ainsi que les directions de travail projetées. Nos méthodes sont typiques de l’analyse dynamique d’algorithmes: elles sont fondées sur les proprietés du système dynamique euclidien (qui est sous-jacent au problème), nous utilisons notamment l' opérateur de transfert associé, mais aussi des séries génératrices de Dirichlet et des théorèmes tauberiens.

En conclusion, j’évoquerai aussi une version probabiliste du théorème dit des trois distances, très lié au cadre précédent.

Ce sont des travaux en cours avec Eda Cesaratto, Valérie Berthé, Brigitte Vallée, et Alfredo Viola.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr