Thesis Details
Efektivní algoritmy pro stromové automaty
In this work a novel algorithm for testing language equivalence and inclusion on tree automata is proposed and implemented as a module in the VATA library. First, existing approaches to equivalence and inclusion testing on both word and tree automata are examined. These existing approaches are then modified to create bisimulation up-to congruence algorithm for tree automata and a formal proof of the soundness of the new algorithm is provided. Efficiency of this new approach is compared with existing language equivalence and inclusion testing methods for tree automata, showing the performance of our algorithm on hard cases is often superior.
word automata, tree automata, language equivalence, language inclusion, bisimulation, antichains, bisimulation up-to congruence
Bidlo Michal, doc. Ing., Ph.D. (DCSY FIT BUT), člen
Burget Lukáš, doc. Ing., Ph.D. (DCGM FIT BUT), člen
Grézl František, Ing., Ph.D. (DCGM FIT BUT), člen
Lucká Mária, prof. RNDr., Ph.D. (FIIT STU), člen
Rogalewicz Adam, doc. Mgr., Ph.D. (DITS FIT BUT), člen
@mastersthesis{FITMT21550,
author = "Ond\v{r}ej Vale\v{s}",
type = "Master's thesis",
title = "Efektivn\'{i} algoritmy pro stromov\'{e} automaty",
school = "Brno University of Technology, Faculty of Information Technology",
year = 2019,
location = "Brno, CZ",
language = "czech",
url = "https://www.fit.vut.cz/study/thesis/21550/"
}