Atraktory nekonečných slov

školitel: doc. Ing. Ľubomíra Dvořáková, Ph.D.
e-mail: zobrazit e-mail
typ práce: bakalářská práce, diplomová práce
zaměření: MI_MM, MI_AMSM, MINF
klíčová slova: atraktory, nekonečná slova, Thueovo-Morseovo slovo
popis:

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ů.

literatura:
  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
naposledy změněno: 26.02.2023 09:57:55

za obsah této stránky zodpovídá: Čestmír Burdík | naposledy změněno: 9.9.2021
Trojanova 13, 120 00 Praha 2, tel. +420 770 127 494
České vysoké učení technické v Praze | Fakulta jaderná a fyzikálně inženýrská | Katedra matematiky