Detail práce

Efektivní algoritmy pro stromové automaty

Diplomová práce Student: Valeš Ondřej Akademický rok: 2018/2019 Vedoucí: Lengál Ondřej, Ing., Ph.D.
Název anglicky
Efficient Algorithms for Tree Automata
Jazyk práce
český
Abstrakt

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.

Klíčová slova

slovní automaty, stromové automaty, jazyková ekvivalence, jazyková inkluze, bisimulace, antichainy, bisimulation up-to congruence

Ústav
Studijní program
Informační technologie, obor Inteligentní systémy
Soubory
Stav
obhájeno, hodnocení A
Obhajoba
17. června 2019
Oponent
Průběh obhajoby

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.

Otázky u obhajoby
  1. Uvěďte příklad (praktického) problému, kde se Vámi navržený algoritmus dá použít.
Komise
Zbořil František, doc. Ing., Ph.D. (UITS FIT VUT), předseda
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
Citace
VALEŠ, Ondřej. Efektivní algoritmy pro stromové automaty. Brno, 2019. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2019-06-17. Vedoucí práce Lengál Ondřej. Dostupné z: https://www.fit.vut.cz/study/thesis/21550/
BibTeX
@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/"
}
Nahoru