Detail práce

Kongruence pro stromové automaty

Bakalářská práce Student: Žufan Petr Akademický rok: 2016/2017 Vedoucí: Holík Lukáš, doc. Mgr., Ph.D.
Název anglicky
Congruences for Tree Automata
Jazyk práce
český
Abstrakt

Tento článek pojednává o testování ekvivalence stromových automatů (TA). Přináší nový algoritmus vycházející z algoritmu Bonchiho a Pouse pro slovní automaty. Tento nový algoritmus spojuje bisimulaci s determinizací za běhu. Pomocí optimalizace založené na kongruenčním uzávěru se snaží vyhýbat extrémnímu zvětšování stavového prostoru. Z tohoto hlediska je lepší než jiné metody pro tento problém.

Klíčová slova

automat, stromový automat, inkluze jazyků, ekvivalence jazyků, kongruence

Ústav
Ústav inteligentních systémů FIT VUT v Brně
Studijní program
Informační technologie
Soubory
Stav
obhájeno, hodnocení C
Obhajoba
13. června 2017
Oponent
Janků Petr, Ing.
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 dobře (C).

Otázky u obhajoby
  1. Vysvětlete proč Vámi implementovaný algoritmus ekvivalence zpracováva automaty zdola-nahoru, když VATA podporuje opačný formát?
  2. Co by bylo potřeba udělat, aby Vámi implementovaný algoritmus ekvivalence zpracovával automaty shora-dolů?
Komise
Honzík Jan M., prof. Ing., CSc. (UIFS FIT VUT), předseda
Janoušek Vladimír, doc. Ing., Ph.D. (UITS FIT VUT), člen
Novák Michal, doc. RNDr., Ph.D. (UMAT FEKT VUT), člen
Strnadel Josef, Ing., Ph.D. (UPSY FIT VUT), člen
Szőke Igor, Ing., Ph.D. (UPGM FIT VUT), člen
Citace
ŽUFAN, Petr. Kongruence pro stromové automaty. Brno, 2017. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2017-06-13. Vedoucí práce Holík Lukáš. Dostupné z: https://www.fit.vut.cz/study/thesis/19744/
BibTeX 
@bachelorsthesis{FITBT19744,
    author = "Petr \v{Z}ufan",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Kongruence 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 = 2017,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/19744/"
}

Závěrečné práce

Nahoru