Rigo, Michel[Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Handbook of Automata
[en] from Mathematics to Applications
European Math. Society Publishing house
[en] Numeration systems ; Recognizable sets ; Cobham's theorem ; Ultimate periodicity ; Dynamical systems ; Substitutions
[en] Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 states that if a set of integers is both k-recognizable and ℓ-recognizable, then it is a finite union of arithmetic progressions. We present several extensions of this result to nonstandard numeration systems, we describe the relationships with substitutive and automatic words and list Cobham-type results in various contexts.