Original title: Kongruence pro stromové automaty
Translated title: Congruences for Tree Automata
Authors: Žufan, Petr ; Janků, Petr (referee) ; Holík, Lukáš (advisor)
Document type: Bachelor's theses
Year: 2017
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tento článek pojednává o testování ekvivalence stromových automatů (TA). Přináší nový algoritmus vycházející z algoritmu Bonchiho a Pouse pro slovní automaty. Tento nový algoritmus spojuje bisimulaci s determinizací za běhu. Pomocí optimalizace založené na kongruenčním uzávěru se snaží vyhýbat extrémnímu zvětšování stavového prostoru. Z tohoto hlediska je lepší než jiné metody pro tento problém. 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: congruence; language equivalence; language inclusion; state machine; tree automata; automat; ekvivalence jazyků; inkluze jazyků; kongruence; stromový automat

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/69852

Permalink: http://www.nusl.cz/ntk/nusl-364157


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses