Towards Automaticity aspects of combinatorial complexity functions

There are several ways to quantify the complexity of an infinite word. Quite often, this is done by considering its finite factors (or contiguous blocks). For example, the factor complexity function (counting the number of distinct blocks of a given length) reveals interesting global properties of the word, and the notion has been applied successfully, e.g., in transcendental number theory. Other combinatorial complexity functions have also been introduced in recent years.

When a sequence has a finite description (e.g., the Thue-Morse word is generated by a DFA with output), one might hope that its combinatorial complexity functions also have finite descriptions (e.g., the Thue-Morse word’s factor complexity function is given by a regular sequence, or a Z-weighted automaton). In this talk, I will give a brief overview of automatic aspects of combinatorial complexity functions of automatic sequences and discuss some recent results about the so-called binomial complexity functions (functions that count factors up to similarity of scattered subword structures) of automatic sequences.