Simulace pro symbolické automaty

Název anglicky

Simulation for Symbolic Automata

Jazyk práce

český

Abstrakt

Symbolické automaty sú podobné klasickým automatom s jedným veľkým rozdielom: prechody sú značené predikátmi definovanými v oddelenej teórii. Toto umožňuje použiť veľké abecedy s pouźitím oveľa menšieho miesta. V tejto práci sa zaoberáme výpočtom simulácie (binárnej relácie nad množinou stavov, ktorá aproximuje jazykovú inklúziu) pre tieto automaty. Táto relácia sa dá potom použiť pri redukovaní počtu stavov bez nutnosti determinizácie. Existuje niekoľko algoritomv pre výpočet simulácie pre Kripkeho štruktúry, ktoré boli neskôr modifikované pre označené prechodové systémy a klasické automaty. V tejto práci ukážeme ako sa dá jeden z týchto algoritmov modifikovať pre symbolické automaty použitím rozkladu domény abecedy ktorý je kompatibilný s predikátmi značiacimi prechody a použitím možností teórie abecedy.

Klíčová slova

symbolický automat, simulácia, redukcia automatov

Ústav

Ústav inteligentních systémů FIT VUT v Brně

Studijní program

Informační technologie

Soubory

Stav

obhájeno, hodnocení A

Obhajoba

13. června 2017

Oponent

Lengál Ondřej, Ing., Ph.D.

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 výborně (A).

Otázky u obhajoby

Čím si vysvětlujete tak dobré experimentální výsledky algoritmu NoCountSFA (v porovnání s "chytřejšími'' algoritmy), který nepoužívá čítače, jež jsou v ne-symbolické verzi klíčové k dobrému výkonu algoritmu?

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

SÍČ, Juraj. Simulace pro symbolické 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/19745/

BibTeX

@bachelorsthesis{FITBT19745,
    author = "Juraj S\'{i}\v{c}",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Simulace pro symbolick\'{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/19745/"
}