Ing. Štěpán Starosta, Ph.D. (externí spolupracovník)

www: http://
 

témata prací

Efektivní datová struktura pro pseudopalindromické vlastnosti faktorových jazyků

školitel: doc. Ing. Štěpán Starosta, Ph.D.
e-mail: zobrazit e-mail
typ práce: bakalářská práce, diplomová práce
zaměření: MI_MM, MI_AMSM, MINF
klíčová slova: datové struktury, palindromy, kombinatorika na slovech
popis: Výskyt palindromů, slov stejných při čtení zprava i zleva, v nekonečných slovech, je spojen s mnoha zkoumanými vlastnostmi, například palindromická komplexita, palindromický defekt a symetrie v jazyku daného nekonečného slova. Nejefektivnější známou datovou strukturou, která umožňuje zkoumat výskyty palindromů, je EERTREE [1]. Tématem práce je zobecnit tuto datovou strukturu pro konkrétní specifické vlastnosti a pro tzv. pseudopalindromy, či jiné druhy symetrií v jazyce daného slova.
literatura: [1] Mikhail Rubinchik, Arseny M. Shur, EERTREE: An efficient data structure for processing palindromes in strings, European Journal of Combinatorics, Volume 68, 2018, Pages 249-265, ISSN 0195-6698, https://doi.org/10.1016/j.ejc.2017.07.021
naposledy změněno: 26.04.2018 22:36:55

Injektivita a symetrie v jazykách generovaných morfismem

školitel: doc. Ing. Štěpán Starosta, Ph.D.
e-mail: zobrazit e-mail
typ práce: bakalářská práce, diplomová práce
zaměření: MI_MM, MI_AMSM, MINF
klíčová slova: kombinatorika na slovech, morfizmus, symetrie jazyků
popis: Nekonečné slovo, tedy posloupnosti symbolů z konečné abecedy, lze definovat tak, že bude pevným bodem nějakého morfismu. Například na abecedě {a,b} je pevným bodem morfismu, který je definovaný pomocí obrazů písmen jako a->ab,b->a, slovo abaababaab... Tématem práce by bylo určování některých vlasností takto vygenerováného nekonečného slova bez nutnosti extenzivního procházení delších a delších podslov. Mezi tyto vlastnosti patří především symetrie v jazyku, například uzavřenost na zrcadlení (s každým podslovem obsahuje nekonečné slovo i podslovo čtené z druhé strany) či vůbec injektivita morfismu na jazyku, který generuje (na množině všech podslov generovaného nekonečného slova). Výchozím bodem zkoumání je pohled na morfismy a jejich pevné body v [1].
literatura: [1] Sébastien Labbé, Edita Pelantová, Štěpán Starosta, On the Zero Defect Conjecture, European Journal of Combinatorics, Volume 62, 2017, Pages 132-146, ISSN 0195-6698, https://doi.org/10.1016/j.ejc.2016.12.006
naposledy změněno: 26.04.2018 22:35:26

za obsah této stránky zodpovídá: Radek Fučík | naposledy změněno: 7.8.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