Thesis Details

Kongruence pro stromové automaty

Bachelor's Thesis Student: Žufan Petr Academic Year: 2016/2017 Supervisor: Holík Lukáš, doc. Mgr., Ph.D.
English title
Congruences for Tree Automata
Language
Czech
Abstract

This thesis discusses testing of tree automata (TA) equivalence. We propose a new algorithm based on Bonchi Pouse's algorithm of word automata. The new algortihm combines bisimulation and determinization on the fly. Using an optimalization based on congruence closure, we try to avoid extreme expansion of state space. From this point of view, the new algorithm is better than others.

Keywords

state machine, tree automata, language inclusion, language equivalence, congruence

Department
Department of Intelligent Systems FIT BUT
Degree Programme
Information Technology
Files
Status
defended, grade C
Date
13 June 2017
Reviewer
Janků Petr, Ing.
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
ŽUFAN, Petr. Kongruence pro stromové 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/19744/
BibTeX 
@bachelorsthesis{FITBT19744,
    author = "Petr \v{Z}ufan",
    type = "Bachelor's thesis",
    title = "Kongruence pro stromov\'{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/19744/"
}

Theses

Back to top