黑料网

Abstract: Classically, an infinite words’ complexity has been studied through its finite factors. The factor complexity function (which counts the number of distinct factors for each length) of an infinite word already reveals interesting structural properties of the word (e.g., aperiodicity). In recent years other complexity functions have been introduced to varying success. In this talk I will consider the so-called abelian and binomial complexity functions of a particular class of infinite words. The former complexity function counts the number of anagram classes of a given length, while the latter counts factors up to similarity of subword structures.

The family of infinite words I will focus on are a subfamily of automatic sequences. Automatic sequences enjoy several characterisations; for this talk, the important characterisations are that they are 1) generated by word homomorphisms of uniform image length of letters; 2) generated by DFAs with output; and 2) are those words that are definable in Büchi arithmetic. In this talk we will explore how counting functions, such as the factor and abelian complexity functions, of automatic sequences can themselves be generated by automata (at least for a particular subclass of automatic sequences).

I will give an overview of what is known about the automaticities of counting functions and touch upon my research, joint with M. Rigo and M. Stipulanti, in this topic. The talk will be self-contained and accessible to a wider audience within theoretical CS.