| Meno: | Michal |
|---|---|
| Priezvisko: | Jánošík |
| Názov: | Opisná zložitosť regulárnych jazykov a MSO logika |
| Vedúci: | doc. RNDr. Peter Kostolányi, PhD. |
| Rok: | 2026 |
| Kľúčové slová: | regulárne jazyky, monadická logika druhého rádu, opisná zložitosť |
| Abstrakt: | V tejto práci je predstavená Büchiho-Elgotova-Trachtenbrotova veta, čiže prepojenie regulárnych jazykov a monadickej logiky druhého rádu. Práca obsahuje dôkaz tejto vety, v ktorom sú odstránené niektoré nedostatky dôkazov vyskytujúcich sa v literatúre. Taktiež sú v nej uvedené príklady konštrukcie konečných automatov ekvivalentných danej formule. Keďže opisná zložitosť regulárnych jazykov v kontexte MSO logiky nebola doteraz príliš skúmaná, nie sú ustálené miery zložitosti pre formuly MSO logiky vhodné na jej skúmanie. V tejto práci je niekoľko takýchto mier navrhnutých a pomocou nich sú dokázané horné odhady na opisnú zložitosť transformácie konečného automatu na MSO formulu a naopak. |
Súbory bakalárskej práce:
| Bakalarska_praca_Janosik.pdf |
Súbory prezentácie na obhajobe: