Seminar - Journées Louis Antoine

Boris Adamczewski (CNRS, Marseille)

Automates finis, arithmétique et équations fonctionnelles

Parmi les suites infinies à valeurs dans un ensemble fini, ou parmi les ensembles d'entiers naturels, certains sont très réguliers comme les suites périodiques ou les progressions arithmétiques, tandis que d'autres, tels que les suites et les ensembles aléatoires, ne peuvent être décrits de façon simple. Les automates finis forment une classe de machines de Turing particulièrement rudimentaires qui joue un rôle important en informatique. En théorie des nombres, ces machines sont utilisées pour définir des suites et des ensembles dits « automatiques ». Un des principaux intérêts de ces structures automatiques est qu'elles jouissent d une forte régularité sans pour autant être triviales. Elles se situent ainsi quelque part entre ordre et chaos, même si, par bien des aspects, leur régularité prévaut. Cette caractéristique conduit à de nombreuses applications de la théorie des automates finis à la théorie des nombres.

Le but de ce mini-cours est de présenter de telles applications en insistant sur le fait que les séries génératrices associées aux suites ou aux ensembles automatiques satisfont à des équations fonctionnelles particulières, appelées équations mahlériennes.

Mireille Bousquet-Mélou (CNRS, Bordeaux)

Marches au hasard dans des cônes: dénombrement et complexité