Original title: Redukce nedeterministických konečných automatů
Translated title: Reduction of the Nondeterministic Finite Automata
Authors: Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Document type: Master’s theses
Year: 2011
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Nedeterministický konečný automat je důležitým nástrojem, který se používá pro zpracování řetězců v mnoha různých oblastech programování. V rámci zvýšení efektivity programů je důležité snažit se o zmenšování jeho velikosti. Tento problém je však velmi výpočetně náročný, proto je potřeba hledat nové postupy. V této práci jsou uvedeny základy konečných automatů a poté jsou představeny různé metody zabývající se jejich redukcí. Použitelné redukční algoritmy jsou v práci podrobněji popsány, dále implementovány a otestovány. Nakonec jsou výsledky zhodnoceny. Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
Keywords: breadth first search; equivalence; minimalization; minimization; NFA; nondeterministic finite automaton; preorder; reduction; SAT solver; satisfiability problem; ekvivalence; kvaziuspořádání; minimalizace; nedeterministický konečný automat; NKA; problém splnitelnosti; prohledávání do šířky; předuspořádání; redukce

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/54175

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


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