Thesis Details

Simulace pro symbolické automaty

Bachelor's Thesis Student: Síč Juraj Academic Year: 2016/2017 Supervisor: Holík Lukáš, doc. Mgr., Ph.D.
English title
Simulation for Symbolic Automata
Language
Czech
Abstract

Symbolic automata are similar to classical automata with one big difference: transitions are labelled with predicates defined in separate logical theory. This allows usage of large alphabets while taking less space. In this work we are interested in computing simulation (a binary relation on states that language inclusion) for these automata. This can be then used for reducing the size of automata without the need to determinize them first. There exist few algorithms for computing simulation over Kripke structures, which were then altered to work over labeled transition systems and classical automata. We show how one of these algorithms can be modified for symbolic automata by using the partition of the alphabet domain that is compatible with the predicates labelling transitions and by using the possibilities of the alphabet theory.

Keywords

symbolic automata, simulation, reduction of automata

Department
Degree Programme
Information Technology
Files
Status
defended, grade A
Date
13 June 2017
Reviewer
Committee
Honzík Jan M., prof. Ing., CSc. (DIFS FIT BUT), předseda
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Novák Michal, doc. RNDr., Ph.D. (DMAT FEEC BUT), člen
Strnadel Josef, Ing., Ph.D. (DCSY FIT BUT), člen
Szőke Igor, Ing., Ph.D. (DCGM FIT BUT), člen
Citation
SÍČ, Juraj. Simulace pro symbolické automaty. Brno, 2017. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2017-06-13. Supervised by Holík Lukáš. Available from: https://www.fit.vut.cz/study/thesis/19745/
BibTeX
@bachelorsthesis{FITBT19745,
    author = "Juraj S\'{i}\v{c}",
    type = "Bachelor's thesis",
    title = "Simulace pro symbolick\'{e} automaty",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2017,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/19745/"
}
Back to top