Seminar • Algorithms and Complexity • Minimal (Asymptotic) Critical Exponent of Balanced Sequences

Please note: This seminar will take place in DC 1304 and virtually over Zoom.

Daniela Opocenska, Exchange Graduate Student

This topic is actually combinatorics on words. Balanced sequences can be generated using well-known Sturmian sequences, and they retain many similar characteristics. The critical exponent is the upper limit of successive repetitions of factors in a given sequence. The obvious question is whether it is possible to avoid a certain number of repetitions in a sequence over a given alphabet. The general lower bound is well known, but only a conjecture was known for balanced sequences.

In my bachelor thesis, we worked on an algorithm for computing the (asymptotic) critical exponent of balanced sequences, which is independent of the size of the alphabet, and its subsequent implementation. We managed to refute the original conjecture. We found a smaller lower bound for d > 10 and showed that it is attained for even-sized alphabets.

Now, we work with the asymptotic critical exponent of balanced sequences. It is defined as the upper limit of the maximal repetition of factors of length n. We provide a method which enables us to find a d-ary balanced sequence with the least asymptotic critical exponent for 1 < d < 11.

To attend this seminar in person, please go to DC 1304. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/95630024524.