Events

Date: 29 January 2026   Time: 13:00 - 14:00     

Location: MB-503

Infinite words can be used to encode interesting properties of the orbits of discrete dynamical systems. Analysing the complexity of such a system may then be analysed through this encoding. Combinatorially speaking, quite often its complexity is measured through its finite factors, or finite contiguous blocks appearing in the infinite encoding. 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 an infinite word has a finite description (e.g., it is generated by a Deterministic Finite Automaton with Output (DFAO)), one might hope that its combinatorial complexity functions also have finite descriptions (e.g., given by a weighted automaton over the integers). In this talk, I will give an overview of automatic aspects of combinatorial complexity functions of sequences generated by DFAOs and discuss some recent results and ongoing research about the so-called binomial complexity functions (functions that count factors up to similarity of scattered subword structures) of automatic sequences.

The talk is based on joint work with M. Rigo, M. Stipulanti, and N. Wingate.