Syntactic monoid and numeration systems

La complexité en nombre d'états (state complexity) d'un langage régulier est le nombre d'états de son automate minimal. La complexité syntaxique est le cardinal du monoïde syntaxique associé. La première ne prend en compte que le contexte à droite alors la seconde considère les contextes à gauche et à droite. Nous nous intéressons aux liens entre les nombres et leurs représentations. Dans le système décimal, un nombre est pair si sa représentation se termine par 0, 2, 4, 6 ou 8, ce qui donne lieu à ensemble de représentations simple, c'est-à-dire reconnu par automate. Plus généralement, dans une base entière, tout critère de divisibilité se traduit par un automate. Etant donné un ensemble d'entiers, nous voulons répondre aux questions suivantes. Quel est le nombre d'états de l'automate minimal associé. Quelle est la complexité syntaxique associée ? Ces questions s'étendent à des numérations plus générales. Ces problèmes sont motivés par des problèmes de décidabilité. Par exemple : étant donné un automate reconnaissant un ensemble d'entiers, décider si cet ensemble est ou non ultimement périodique