Contribution to collective works (Parts of books)
On Cobham's theorem
Durand, Fabien; Rigo, Michel
2021In Pin, Jean-Eric (Ed.) Handbook of Automata Theory
Peer reviewed
 

Files


Full Text
Chapter26.pdf
Author postprint (525.19 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Numeration systems; Recognizable sets; Cobham's theorem; Ultimate periodicity; Dynamical systems; Substitutions
Abstract :
[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
ISBN/EAN :
9783985470037
Pages :
947-986
Peer reviewed :
Peer reviewed
Commentary :
2010 Mathematics Subject Classification: 68Q45, 68R15, 11B85, 11A67, 11U05, 37B20
Available on ORBi :
since 25 May 2010

Statistics


Number of views
380 (49 by ULiège)
Number of downloads
348 (24 by ULiège)

Bibliography


Similar publications



Contact ORBi