Séminaire Combinatoire et Théorie des Nombres ICJ

An asymptotic version of Cobham's theorem

by Jakub Konieczny

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

Bât. Braconnier, salle Fokko du Cloux

ICJ, Université Lyon 1


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.