Résumé :

En combinatoire des mots, il est courant de compter le nombre de motifs spécifiques apparaissant dans une suite infinie. En effet, de nombreux travaux sont consacrés à l’étude de la célèbre complexité en facteurs, c’est-à-dire le nombre de facteurs (blocs continus de lettres) différents. Une variante bien connue est la complexité abélienne, où les facteurs sont comptés à équivalence abélienne près, c’est-à-dire à permutation des lettres près. Dans cet exposé, nous discuterons du concept relativement peu exploré de la complexité additive, qui compte les facteurs à équivalence additive près. Deux facteurs sont dits additivement équivalents s’ils sont de même longueur et que la somme des lettres qui les composent est la même. Notre contribution consiste à élargir les connaissances générales sur la complexité additive d'un point de vue théorique et à examiner divers exemples bien connus en combinatoire des mots. En particulier, nous utilisons le formalisme de la logique et le logiciel Walnut pour décider des propriétés liées aux suites automatiques. Ce travail est en collaboration avec Jeffrey Shallit et Manon Stipulanti.