Séminaire Combinatoire et Théorie des Nombres ICJ
# An asymptotic version of Cobham's theorem

→
Europe/Paris

Bât. Braconnier, salle Fokko du Cloux (ICJ, Université Lyon 1)
### Bât. Braconnier, salle Fokko du Cloux

#### ICJ, Université Lyon 1

Description

Cobham's theorem is one of the most fundamental results in the theory of automatic sequences, that is, sequences whose n-th term can be computed by a finite automaton which receives as input the expansion of n in a given base k. The theorem asserts, roughly speaking, that a sequence cannot be computed by finite automata in two different bases, except for the arguably trivial cases where the bases are multiplicatively dependent (and hence lead to the same notion of automaticity) or if the sequence is eventually periodic (and hence automatic in each base). Over the years, many extensions and analogues of this theorem have been established. During my talk, I will introduce an asymptotic analogue of the notion of an automatic sequence and show that such asymptotically automatic sequences obey a variant of Cobham's theorem.