Nekonečná slova s nízkou faktorovou komplexitou

školitel: doc. Ing. Ľubomíra Dvořáková, Ph.D.
e-mail: zobrazit e-mail
typ práce: dizertační práce
zaměření: MI_MM, MINF
klíčová slova: dendric sets, tree sets, factor complexity, S-adic representation
popis:

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.

literatura:
  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
naposledy změněno: 09.11.2019 17:35:16

za obsah této stránky zodpovídá: Ľubomíra Dvořáková | naposledy změněno: 12.9.2011
Trojanova 13, 120 00 Praha 2, tel. 224 358 540, pevná linka 224 923 098, fax 234 358 643
České vysoké učení technické v Praze | Fakulta jaderná a fyzikálně inženýrská | Katedra matematiky