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

The aim of the proposed project is to obtain optimization results for the ground-state energy in a family of model quantum systems with magnetic fields and non-trivial geometry.

From the mathematical point of view, it means that there is a differential operator on a domain that describes the magnetic system, and the goal is to show that its smallest eigenvalue attains the maximal or the minimal value for some specific shape. Typically, the optimal shape for the ground-state energy is radially symmetric [1, 3], and it can, for example, be the disk or the annulus. Optimization with magnetic fields is much less understood than without them and even very fundamental questions remain open [2], but it is certainly possible to select the setting, which is feasible to analyze within the bachelor or diploma project. The outcome of the project is expected to be a rigorous mathematical proof that certain shape optimizes the ground-state energy. On the level of the bachelor project partial results in this direction will also be sufficient.

1. L. Erdos, Rayleigh-type isoperimetric inequality with a homogeneous magnetic field, Calc. Var. PDE 4 (1996), 283-292.
2. S. Fournais and B. Helffer, Inequalities for the lowest magnetic Neumann eigenvalue, Lett. Math. Phys. 109 (2019), 1683-1700. http://arxiv.org/pdf/1706.01950.pdf
3. A. Kachmar and V. Lotoreichik, On the isoperimetric inequality for the magnetic Robin Laplacian with negative boundary parameter, http://arxiv.org/pdf/2108.05256.pdf

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