Petra Staynova

On Arithmetic Progressions in Substitution Sequences

In this talk we consider right-infinite words over a finite alphabet, which are generated via substitution rules. A well-known way of studying complexity of these words is via the question 'how many finite subwords of a given length does this infinite word have?', which gives rise to the notion of subword complexity. If instead one considers what types of (finite) subwords occur as arithmetic subsequences, one can obtain a different and very interesting measure of complexity. In this talk, we consider the occurrence of monochromatic (i.e. same letter) arithmetic progressions within right-infinite words, and provide asymptotic growth rates in some (general) cases. No previous knowlege is assumed, and the talk will start from the basics of subsitution systems.