Sčítání na nekonečných slovech

školitel: Ing. Ľubomíra Dvořáková, Ph.D.
e-mail: zobrazit e-mail
typ práce: bakalářská práce
zaměření: MI_MM, MI_AMSM, II_SIMI
klíčová slova: kombinatorika na slovech, sturmovská slova, Roteova slova
popis:

Uvažujeme-li binární nekonečná slova nad abecedou {0,1}, pak operací sčítání mod 2 vzniká ze slova u=u_0 u_1... slovo S(u), jehož i-té písmeno je rovno u_i+u_{i+1} mod 2. Tato operace se objevuje v řadě oblastí kombinatoriky na slovech. Uveďme nejprve, že komplexita nekonečného slova u je funkce C, která v bodě n udává počet různých faktorů délky n slova u. Je známý vztah mezi Roteovými slovy (slova s komplexitou C(n)=2n a uzavřená na výměnu nul a jedniček) a sturmovskými slovy (aperiodická slova s nejnižší možnou komplexitou): Nekonečné slovo u je Roteovo, právě když slovo S(u) je sturmovské. Viz [2]. Působení operace S na defekt nekonečných slov bylo studováno v článku [1], přičemž defekt měří, kolik pozic v nekonečném slově nepřináší žádný nový palindrom. Má-li slovo u konečný defekt, pak S(u) má také konečný defekt. V bakalářské práci [3] bylo studováno působení operace S na privilegovaná slova a na defekt slov získaných tzv. palindromickým uzávěrem.

Cílem této práce bude studovat působení operace S na různé kombinatorické vlastnosti nekonečných slov.

Rešeršní část práce

  1. Studium kombinatoriky na slovech.
  2. Nastudování dosavadních výsledků týkajících se operace S.

Výzkumná část práce

  1. Studium působení operace S na různé kombinatorické vlastnosti: komplexita, palindromická komplexita, frekvence faktorů, substitutivita, návratová slova apod.
  2. Zobecnění výsledků pro větší abecedy.

literatura:
  1. Pelantová E., Starosta Š.: Constructions of words rich in plaindromes, arXiv:1409.2354 (2014)
  2. Rote G.: Sequences with subword complexity 2n, Journal of Number Theory 46 (1994), 196--213
  3. Velká T.: Palindromy a privilegovaná slova, bakalářská práce (2014/2015), FJFI ČVUT v Praze
naposledy změněno: 22.07.2015 20:09:27

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