7 décembre 2015
Alexis Bès (LACL)Dans cet exposé de synthèse, on s’intéressera aux ensembles d’entiers reconnaissables par automate fini lorsqu’on lit les entiers en base k>=2. On montrera qu’il existe plusieurs caractérisations de ces ensembles, notamment en termes de substitutions et en termes de définissabilité logique. On verra également que ces propriétés sont sensibles à la base k choisie (théorème de Cobham). Puis on se concentrera sur l’approche logique, en montrant comment on peut aborder certains problèmes combinatoires et algorithmiques du domaine en utilisant des arguments de définissabilité et décidabilité (et des prouveurs automatiques).