[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.
Disciplines :
Computer science Mathematics
Author, co-author :
Durand, Fabien
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
On Cobham's theorem
Publication date :
2021
Main work title :
Handbook of Automata Theory
Main work alternative title :
[en] Automata in Mathematics and Selected Applications
Author, co-author :
Pin, Jean-Eric
Publisher :
European Math. Society Publishing house, Zurich, Switzerland