Detail práce

Minimization of Counting Automata

Diplomová práce Student: Turcel Matej Akademický rok: 2020/2021 Vedoucí: Holík Lukáš, doc. Mgr., Ph.D.
Název česky
Minimalizace automatů s jednoduchými čítači
Jazyk práce
anglický
Abstrakt

Táto práca sa zaoberá redukciou veľkosti tzv. čítačových automatov. Čítačové automaty rozširujú klasické konečné automaty o čítače s obmedzeným rozsahom hodnôt. Umožňujú tým efektívne spracovať napr. regulárne výrazy s opakovaním: a{5,10}. V tejto práci sa zaoberáme reláciou simulácie v čítačových automatoch, pomocou ktorej sme schopní zredukovať ich veľkosť. Opierame sa pritom o klasickú simuláciu v konečných automatoch, ktorú netriviálnym spôsobom rozširujeme na čítačové automaty. Kľúčovým rozdielom je nutnosť simulovať okrem stavov taktiež čítače. Za týmto účelom zavádzame nový koncept parametrizovanej relácie simulácie, a navrhujeme metódy výpočtu tejto relácie a redukcie veľkosti čítačových automatov pomocou nej. Navrhnuté metódy sú tiež implementované a je vyhodnotená ich efektivita.

Klíčová slova

čítačový automat, simulácia, redukcia automatov

Ústav
Ústav inteligentních systémů FIT VUT v Brně
Studijní program
Informační technologie, obor Matematické metody v informačních technologiích
Soubory
Stav
neobhájeno
Obhajoba
23. června 2021
Oponent
Vojnar Tomáš, prof. Ing., Ph.D.
Průběh obhajoby

Student se nedostavil.

Otázky u obhajoby
  1. Mohl byste charakterizovat blíže automat s omezenými čítači (a regulární výraz, ze kterého původně vznikl), na kterém jste dosáhl Vámi zmiňované nejlepší procentuální redukce (82 % na str. 67)?
  2. Je vždy simulační redukce procentuálně ostře lepší než bisimulační, jak uvádíte na straně 66?
  3. Neměla by na str. 27 v bodě 2(b) ve větě "We thus also require that..." být použita inverze beta s apostrofem?
  4. Je použití Exit1 na straně 30 v bodě (II)4(a) správně?
Komise
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (UITS FIT VUT), předseda
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Malinka Kamil, Mgr., Ph.D. (UITS FIT VUT), člen
Očenášek Pavel, Mgr. Ing., Ph.D. (UIFS FIT VUT), člen
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT), člen
Citace
TURCEL, Matej. Minimization of Counting Automata. Brno, 2021. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2021-06-23. Vedoucí práce Holík Lukáš. Dostupné z: https://www.fit.vut.cz/study/thesis/24072/
BibTeX 
@mastersthesis{FITMT24072,
    author = "Matej Turcel",
    type = "Diplomov\'{a} pr\'{a}ce",
    title = "Minimization of Counting Automata",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2021,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/24072/"
}

Závěrečné práce

Nahoru