Abstract: 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.
An asymptotic version of Cobham's theorem
25.10.2022 15:15 - 16:45
Organiser:
Ch. Krattenthaler
Location:
Wiedner Hauptstrasze 8-10, Institut fuer Diskrete Mathematik und Geometrie, Dissertantenzimmer, 8. Stock, Turm A