Семинар МЛ ТИ: "Non-constructive approach to repetition thresholds"
В среду, 18 октября, приглашаем Вас на семинар лаборатории теоретической информатики.
Семинар пройдет онлайн с 18:10 до 19:30.
Название: Non-constructive approach to repetition thresholds
Докладчик: Arseny M. Shur
Аннотация: 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.