Graphes de Cayley et suites automatiques

par Pierre Guillot (IRMA, Université de Strasbourg)

mardi 31 mai 2016, 10:45 → 11:45 Europe/Paris

Salle Fokko du Cloux (ICJ)

Les suites dites automatiques sont produites par des automates, qui eux-mêmes sont des graphes orientés sur lesquels on a placé une certaine quantité de décoration. La plupart des suites d'entiers que l'on étudie en combinatoire sont automatiques lorsqu'on les réduit modulo une puissance d'un nombre premier. Les graphes de Cayley, d'un autre côté, sont des graphes orientés obtenus à partir de groupes finis dans lesquels on a choisi des générateurs. Afin de répondre à une question posée par Rowland, on étudie les suites automatiques produites par un graphe de Cayley. Pour les suites 2-automatiques -- c'est-à-dire grosso modo les suites dont le n-ième terme se calcule "facilement" en fonction des chiffres de n écrit en base 2 -- la réponse est particulièrement satisfaisante : une suite donnée provient d'un graphe de Cayley si et seulement si elle possède une certaine symétrie, que nous appelons "auto-similarité". Nous décrirons une application au calcul de certaines fractions rationnelles associées aux suites automatiques.