Automates de suites linéairement récurrentes et addition dans les systèmes de numération abstraits
Jeudi 22 mai 2025, 14:00 à 15:00
(LIFO, université d'Orléans)
Cet exposé est motivé par la question suivante : étant donné un mot infini engendré par une substitution, quand est-il possible de répondre de manière automatisée à des questions exprimables par des prédicats du premier ordre (par exemple : quels sont les longueurs des cubes qui apparaissent comme facteur de ce mot ?) ? Les techniques de Büchi-Bruyère nécessitent de trouver un système de numération pour exprimer ce mot comme un mot automatique et que l'addition dans ce système de numération soit réalisable par un automate fini. Nous introduisons les automates de suites pour étudier l'addition des systèmes de numération de Dumont-Thomas. Lorsque les suites associées ont des relations de récurrence associées à un nombre Pisot, nous produisons un automate fini pour l'addition. Une mise en œuvre permet une utilisation effective dans l'outil Walnut. Ce travail a été réalisé avec O. Carton, JM. Couvreur et M. Delacourt et sera présenté à WORDS 2025 (https://arxiv.org/abs/2406.09868).