Skip to main content

Quasiperiods in infinite words

Guilhem Gamard

This talk deals with combinatorics on infinite words. Intuitively, an infinite word w has a quasiperiod q if w is covered with occurrences of q. For instance, the Fibonacci word 010010100100101001010010010… has the quasiperiod 010. Notice that an infinite word might have several, or even infinitely many quasiperiods. The more quasiperiods it has, the more it can be considered “simple” or “regular”.

First we quickly review properties of words with only one quasiperiod. Then we switch to words with infinitely many quasiperiods, which we call multi-scale quasiperiodic. We give a method (not exactly an algorithm) allowing to determine the set of quasiperiods of an arbitrary infinite word. This method is especially well-suited for morphic words, and we give examples to emphasize this.

The examples also illustrate how quasiperiods of a given word relate to each other.

We finish by showing that quasiperiodicity allows to express well-known properties of symmetry, namely periodicity and Sturmian-ness. Several questions are still open, and can be discussed afterwards if the audience is inspired.



Share this: