Palindromy a privilegovaná slova

š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: palindrom, privilegované slovo, privilegovaná komplexita, slovo bohaté na palindromy
popis:

Privilegovaná slova jsou v kombinatorice na slovech čerstvým pojmem, definována byla teprve v roce 2013. Jejich definice přirozeně plyne z jisté vlastnosti slov bohatých na palindromy: Je známo, že každé konečné slovo obsahuje maximálně tolik palindromů, kolik je jeho délka zvětšená o jedna. Slova, která této meze nabývají, se nazývají bohatá na palindromy. Jejich ekvivalentní charakterizací je fakt, že kompletní návratové faktory k palindromům jsou opět palindromy. Privilegovaná slova byla definována rekurzivně jako slova, která jsou kompletními návratovými slovy ke kratším privilegovaným slovům, přičemž nejkratšími privilegovanými slovy jsou písmena a prázdné slovo.

O privilegovaných slovech se zatím mnoho neví. Bylo dokázáno, že palindromické a privilegované faktory splývají ve slovech bohatých na palindromy. Byla charakterizována sturmovská slova pomocí privilegované komplexity. A byla prostudována privilegovaná komplexita Thueova--Morseova slova.

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

  1. Studium kombinatoriky na slovech.
  2. Nastudování aktuálních článků týkajících se palindromů a privilegovaných faktorů v nekonečných slovech.

Výzkumná část práce

  1. Studium palindromické a privilegované komplexity dalších nekonečných slov.
  2. Zkoumání dalších vlastností palindromů a privilegovaných faktorů v nekonečných slovech.
  3. Vytvoření programu pro výpis privilegovaných faktorů nekonečných slov.

literatura:
  1. Glen A.: Palindromic richness, European Journal of Combinatorics 30 (2009), 510--531
  2. Kellendonk, J., Lenz, D., Savinen, J.: A characterization of subshifts with bounded powers, Discrete Mathematics 313 (2013), 2881--2894
  3. Peltomaki, J.: Introducing priviledged words: Priviledged complexity of sturmian words, Theoretical Computer Science 500 (2014), 57--67
  4. Peltomaki, J.: Priviledged factors in the Thue--Morse word -- A comparison of priviledged words and palindromes, odesláno do Discrete Applied Mathematics (2014)
poznámka: Na tématu pracuje Tereza Velká.
naposledy změněno: 18.09.2014 19:10:22

za obsah této stránky zodpovídá: Radek Fučík | 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