Detail práce
Efektivní algoritmy pro stromové automaty
Cílem této práce je navržení efektivních algoritmů pro testování jazykové ekvivalence a inkluze stromových automatů a dále pak implementace těchto algoritmů jako rozšíření knihovny VATA. Nejprve je provedena rešerše existujících přístupů testování ekvivalence a inkluze slovních i stromových automatů. Z nich poté vychází návrh nového přístupu k testování ekvivalence a inkluze jazyků stromových automatů založený na bisimulaci vzhledem ke kongruenci, ke kterému je představen formální důkaz korektnosti. Součástí práce je také srovnání efektivity představeného algoritmu a již existujících přístupů, které ukazuje, že na obtížných případech je náš algoritmus často lepší než existující přístupy.
slovní automaty, stromové automaty, jazyková ekvivalence, jazyková inkluze, bisimulace, antichainy, bisimulation up-to congruence
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.
- Uvěďte příklad (praktického) problému, kde se Vámi navržený algoritmus dá použít.
Bidlo Michal, doc. Ing., Ph.D. (UPSY FIT VUT), člen
Burget Lukáš, doc. Ing., Ph.D. (UPGM FIT VUT), člen
Grézl František, Ing., Ph.D. (UPGM FIT VUT), člen
Lucká Mária, prof. RNDr., Ph.D. (FIIT STU), člen
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS FIT VUT), člen
@mastersthesis{FITMT21550, author = "Ond\v{r}ej Vale\v{s}", type = "Diplomov\'{a} pr\'{a}ce", title = "Efektivn\'{i} algoritmy pro stromov\'{e} automaty", school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}", year = 2019, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/21550/" }