doc. Ing. Ľubomíra Dvořáková, Ph.D.

Cílem práce bude studium některých charakteristik nedávno definované třídy faktorových jazyků nazvaných dendrické množiny [1]. Tato třída je zajímavá tím, že zobecňuje současně dvě velice podrobně prozkoumané třídy: slova definovaná Arnouxem a Rauzym v [2] a slova kódující výměnu intervalů. Přitom tyto dvě třídy jsou na vícepísmenné abecedě disjunktní. I když se dendrickým množinám věnuje v posledních letech velká pozornost, mnohé jejich charakteristiky zatím nejsou známé. Jedná se např. o kritický exponent, palindromickou komplexitu [3], popis podtřídy slov bohatých na palindromy, resp. zobecněné palindromy [4], vztah balancovaných slov k dendrickým množinám atd. Zdá se, že silným nástrojem při studiu těchto vlastností by mohla být znalost S-adické reprezentace dendrických slov objevená v [5]. Dalším z cílů práce bude i konstrukce nových typů dendrických množin.

1. V. Berthé, C. De Felice, F. Dolce, J. Leroy, D. Perrin, Ch. Reutenauer, G. Rindone, Acyclic, connected and tree sets. Monatsh. Math., 176(4) (2015) 521–550
2. P. Arnoux, G. Rauzy, Représentation géometrique de suites de complexité 2n + 1, Bull. Soc. Math. France 119(2) (1991) 199–2
3. L. Balková, E. Pelantová, Š. Starosta: Sturmian Jungle (or Garden?) on Multiliteral Alphabets, RAIRO Theor. Inf. Appl. 44 (2010) 443-470
4. L. Balková, E. Pelantová, Š. Starosta, Infinite words with finite defect, Adv. Appl. Math. 47 (2011) 562-574
5. V. Berthé, F. Dolce, F. Durand, J. Leroy, D. Perrin, Rigidity and substitutive dendric words, Int. J. of Found. of Comp. Sci., 29(05) (2018) 705-720

1. F. Dolce, L. Dvořáková, E. Pelantová: On balanced sequences and their critical exponent, Theoret. Comput. Sci. 939 (2023), 18-47
2. D. Damanik, D. Lenz: The index of Sturmian sequences. J. Eur. J. Comb. 23 (2002), 23-29
3. L. Dvořáková, D. Opočenská, E. Pelantová, A. M. Shur: On minimal critical exponent of balanced sequences, Theoret. Comput. Sci. 922 (2022), 158-169
4. L. Balková: Factor frequencies in generalized Thue-Morse words, Kybernetika 48(3) (2012), 371-385

Kritický exponent je aktuálně velmi populární téma v oblasti kombinatoriky na slovech. Týká se repetic v nekonečných slovech. Jednoduše řečeno vyjadřuje maximální možnou míru opakování faktorů v daném nekonečném slově. Kritický exponent je známý pro některé třídy slov: sturmovská [1], balancovaná [2], regulární Arnouxova-Rauzyova (AR) slova. Ačkoliv je kritický exponent známý pro balancovaná slova, pro 2-balancovaná slova zůstává otevřenou otázkou. Problémem totiž je, že zatímco pro balancovaná slova existuje velmi šikovná ekvivalentní charakterizace pomocí tzv. barvení sturmovských slov pomocí slov s konstantními mezerami, pro slova 2-balancovaná se žádná podobná charakterizace nezná. Každopádně jsou alespoň popsány třídy 2-balancovaných slov mezi AR slovy [3] a byla definována nová třída 2-balancovaných slov, která vzniknou jako barvení sturmovských slov opět sturmovskými slovy. Právě u těchto tříd by studie začínala.

Téma je vhodné pro studenty se znalostí programování, ale není to nutnou podmínkou.

1. D. Damanik, D. Lenz: The index of Sturmian sequences. J. Eur. J. Comb. 23 (2002), 23-29
2. L. Dvořáková, D. Opočenská, E. Pelantová, A. M. Shur: On minimal critical exponent of balanced sequences, Theoret. Comput. Sci. 922 (2022), 158-169
3. V. Berthé, J. Cassaigne, W. Steiner: Balance properties of Arnoux-Rauzy sequences. Int. J. Algebra Comput. 23(04) (2013), 689-703

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