Nekonečná slova generovaná více antimorfismy

š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, MINF, APIN
klíčová slova: antimorfismus, palindrom, sturmovské slovo, uzávěr, pseudopalindrom
popis:

V kombinatorice na slovech jsou hojně studována sturmovská slova. Jde vlastně o nekonečná slova generovaná jedním antimorfismem, a to zrcadlením. Konkrétně jde o konstrukci pomocí palindromického uzávěru (konstrukce navržena v roce 2001 v [4]). V roce 2006 v [5] pak byla konstrukce zobecněna na pseudopalindromický uzávěr, kdy jsou slova generována jedním antimorfismem, a na zobecněný pseudopalindromický uzávěr, kdy jsou slova generována více antimorfismy. Mezi slova, která jsou generována takovou zobecněnou konstrukcí (říkáme jim zobecněná pseudostandardní slova), patří další slavné Thueovo-Morseovo slovo a také Roteova slova. Vlastnosti slov vzniklých uzávěry jsou z velké části neprozkoumané.

V článku [1] byla studována komplexita binárních zobecněných pseudostandardních slov a byl nalezen protipříklad k domněnce z článku [6] týkající se komplexity. Článek [2] přinesl nutnou a postačující podmínku na periodicitu binárních a ternárních zobecněných pseudostandardních slov. V článku [3] pak byly studovány pevné body morfismů mezi binárními zobecněnými pseudostandardními slovy.

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

  1. Prohloubené studium kombinatoriky na slovech.
  2. Nastudování článků týkajících se sturmovských a episturmovských slov a zobecnění poznatků z nich pro zobecněná pseudostandardní slova.

Výzkumná část práce

  1. Pokračování ve studiu komplexity zobecněných pseudostandardních slov.
  2. Zkoumání pevných bodů zobecněného pseudopalindromického uzávěru.
  3. Hledání pevných bodů morfismů mezi zobecněnými pseudostandardními slovy nad vícepísmennou abecedou.
  4. Zkoumání dalších vlastností zobecněných pseudostandardních slov, případně jiných slov s jazykem uzavřeným na více antimorfismů.

literatura:
  1. Dvořáková, L., Florian, J.: A new estimate on complexity of binary generalized pseudostandard words, Integers -- Electronic Journal of Combinatorial Number Theory 17 (2017), A61
  2. Dvořáková, L., Florian, J.: On Periodicity of Generalized Pseudostandard Words, Electronic Journal of Combinatorics 23(1) (2016), #P1.2
  3. Dvořáková, L., Velká, T.: Fixed points of morphisms among binary generalized pseudostandard words, Integers -- Electronic Journal of Combinatorial Number Theory 18 (2018), A21
  4. Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539--553
  5. de Luca, A., De Luca, A.: Pseudopalindrome closure operators in free monoids, Theoret. Comput. Sci. 362 (2006), 282--300
  6. Massé, A. B., Paquin, G., Tremblay, H., Vuillon, L.: On generalized pseudostandard words over binary alphabet, Journal of Int. Sequences 16 (2013), Article 13.2.11
naposledy změněno: 26.04.2018 23:40:59

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