Atraktory nekonečných slov

Komprimovatelnost a repetice hrají stěžejní úlohu při zpracování textu. Atraktory jsou jedním z měřítek komprimovatelnosti textu. Pojem atraktor slova zavedli Kempa a Prezza [1], jde o množinu pozic ve slově, z nichž každé podslovo (faktor) nějakou protne. Cílem je nacházet atraktory minimální velikosti.

V oblasti kombinatoriky na slovech je aktuálním tématem zkoumání minimálních atraktorů pro faktory nekonečných slov. Dosud jsou známé atraktory pro sturmovská a obecněji episturmovská slova [2], dále pro Thueovo-Morseovo slovo [3] a pro Roteho slova a částečně jsou prozkoumána slova automatická [4]. Další zajímavou třídou k prozkoumání by byla balancovaná slova (která vznikají obarvením sturmovských slov pomocí slov s konstantními mezerami), dále zobecněná Thueova-Morseova slova nebo některé třídy pevných bodů substitucí či obecněji substitutivních slov.

Při výzkumu je dobré domněnky o tvaru atraktorů ověřovat na PC. Programátorské dovednosti se tedy hodí, ale nejsou nutnou podmínkou pro práci na tématu atraktorů.

1. Kempa, D., Prezza, N., At the roots of dictionary compression: string attractors, In: STOC 2018, 827-840, ACM (2018)
2. Dvořáková, Ľ., String attractors of episturmian sequences, arXiv:2211.01660, 2022
3. Kutsukake, K., et al., On repetitiveness measure of Thue-Morse words, In: SPIRE LNCS 12303, 213-220, Springer (2020)
4. Schaeffer, L., Shallit, J., String attractors for automatic sequences, arXiv:2012.06840, 2020