Supervisors

Suitable for

Abstract

Asymptotically automatic sequences - that is, sequences whose n-th term can be computed by a finite automaton given as input the expansion of n in a given base k - have long been studied in theoretical computer science, number theory, combinatorics and algebra, to name just a few. Recently I introduced a notion tentatively dubbed "asymptotically automatic sequence". This class of sequences remains largely unexplored. It's likely that new results can be obtained by minor modifications of existing arguments, while other cases will present more interesting challenges.

The purpose of this project is to see what results on automatic sequences admit a straightforward generalisation to the asymptotic regime, and for which it's possible to construct a counterexample.

The goal is to find at least one, preferably more, existing results on automatic sequences and either generalise it to asymptotically automatic sequences, or to disprove such a generalisation.

Basic results and definitions can be found in: https://arxiv.org/abs/2305.09885

And a variant of Cobham's theorem can be found in: http://arxiv.org/abs/2209.09588

The standard reference for automatic sequences is “Automatic Sequences: Theory, Applications, Generalizations” by J.-P. Allouche and J. Shallit.

Pre-requisites: Familiarity with automatic sequences / regular languages; basic analysis