TCS lab seminar. 18.10.2023 Arseny M. Shur "Non-constructive approach to repetition thresholds"

Описание

We analyze a simple algorithm, transforming an input word into a word avoiding certain repetitions such as fractional powers and undirected powers. This transformation can be made reversible by adding the log of the run of the algorithm to the output. We introduce a compression scheme for the logs; its analysis proves that $(1+\frac{1}{d})$-powers and undirected $(1+\frac{1}{d})$-powers can be avoided over $d+O(1)$ letters. These results are closer to the optimum than it is usually expected from purely information-theoretic considerations.