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, diplomová práce
zaměření: MI_MM, MI_AMSM, II_SIMI
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 [2]). V roce 2006 v [3] 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] se nám podařilo najít nutnou a postačující podmínku na periodicitu zobecněných pseudostandardních slov a protipříklad k domněnce z článku [4] týkající se komplexity.

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ů substitucí mezi zobecněnými pseudostandardními slovy.
  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. Balková, L., Florian, J.: On periodicity and complexity of generalized pseudostandard words, odesláno do Electronic Journal of Combinatorics (2014)
  2. Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001), 539--553
  3. de Luca, A., De Luca, A.: Pseudopalindrome closure operators in free monoids, Theoret. Comput. Sci. 362 (2006), 282--300
  4. 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
poznámka: Na tématu pracuje Josef Florian.
naposledy změněno: 10.10.2014 12:41:46

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