Študijný odbor: Informatika
Študent: Peter Grochal [ contact ]
Školiteľ: prof. RNDr. Rastislav Královič, PhD.
Email: kralovic at dcs dot fmph dot uniba dot sk
Abstrakt: V tejto práci sa zaoberáme skúmaním teórie formálnych jazykov so zameraním na randomizované automaty. Skúmame jednosmerné viachlavé pravdepodobnostné konečné automaty (PFA(k)) s rôznymi modelmi randomizácie, ktoré sa zvyčajne študujú. Najprv formálne definujeme Monte-Carlo a LasVegas randomizácie, potom rôzne chyby, s ktorými takéto automaty môžu rozpoznávať jazyky. Definujeme a dokážeme aj normálny tvar, v ktorom PFA(k) musí v každom kroku výpočtu presunúť aspoň jednu hlavu. Následne skúmame vlastnosti Monte-Carlo a LasVegas PFA(k). Pre všetky tieto modely dokážeme hierarchiu, že s (k + 1)-hlavami majú väčšiu vyjadrovaciu silu ako s k. Tiež skúmame rôzne uzáverové vlastnosti tried rozpoznávaných týmito automatmi ako aj vzťahy medzi týmito triedami. Taktiež definujeme tzv. barely-random PFA(k) a ukážeme, že tieto pravdepodobnostné automaty nemožno amplifikovať, t.j. ukážeme dolný odhad na chybu, s ktorou dokáže taký PFA(k) rozpoznať konkrétny jazyk.
Kľúčové slová: jednosmerné viachlavové pravdepodobnostné konečné automaty, formálne jazyky, pravdepodobnostné automaty, LasVegas randomizácia, Monte-Carlo randomizácia, hierarchia, barely-random pravdepodobnostné automaty, amplifikácia.
Práca - odovzdaná (anglicky): [ pdf ]
Práca - po zapracovaní pripomienok (anglicky): [ pdf ]