| Meno: | Peter
|
|---|
| Priezvisko: | Grochal
|
|---|
| Názov: | Randomized Multi-head Finite Automata
|
|---|
| Vedúci: | prof. RNDr. Rastislav Královič, PhD.
|
|---|
| Rok: | 2023
|
|---|
| Kľúčové slová: | jednosmerné viachlavové pravdepodobnostné konečné automaty, formálne jazyky, LasVegas randomizácia, Monte-Carlo randomizácia, hierarchia, barely-random pravdepodobnostné automaty, amplifikácia.
|
|---|
| 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.
|
|---|