| 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.
|
|---|