Reference : On Cobham's theorem
Parts of books : Contribution to collective works
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
On Cobham's theorem
Durand, Fabien [> >]
Rigo, Michel mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
In press
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.
Researchers ; Professionals ; Students
2010 Mathematics Subject Classification: 68Q45, 68R15, 11B85, 11A67, 11U05, 37B20

File(s) associated to this reference

Fulltext file(s):

Open access
Chapter26.pdfAuthor postprint512.88 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.