Nekonečná slova s nízkou faktorovou komplexitou

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