|
|
Library for Finite Automata and Transducers
Bieliková, Michaela ; Lengál, Ondřej (referee) ; Hruška, Martin (advisor)
Finite state automata are widely used in the field of computer science such as formal verification, system modelling, and natural language processing. However, the models representing the reality are complicated and can be defined upon big alphabets, or even infinite alphabets, and thus contain a lot of transitions. In these cases, using classical finite state automata is not very efficient. Symbolic automata are more concise by employing predicates as transition labels. Finite state transducers also have a wide range of application such as linguistics or formal verification. Symbolic transducers replace classic transition labels with two predicates, one for input symbols and one for output symbols. The goal of this thesis is to design a library for letter and symbolic automata and transducers which will be suitable for fast prototyping.
|
|
|
Gaze-Based Keyboard
Sznapka, Jakub ; Herout, Adam (referee) ; Hradiš, Michal (advisor)
The goal of this bachelor's thesis is to create a tool for gaze typing. It deals with gaze tracking and evalution issues. It contains a description of the Swype method which is used for typing on touch screen devices. Then follows the analysis of different ways which could be used to model the language used by model. The main part is dedicated to design of the gaze typing tool and implementation using the Kaldi toolkit.
|
|
|
Automatic Generator of Diacritics
Veselý, Lukáš ; Sumec, Stanislav (referee) ; Smrž, Pavel (advisor)
The goal of this diploma work is the suggestion and the implementation of the application, which allows adding / removing of diacritics into / from Czech written text. Retrieval "trie" structure is described along with its relation to finite state automata. Further, algorithm for minimization of finite state automata is described and various methods for adding diacritics are discussed. In practical part the implementation in Java programming language with usage of object-oriented approach is given. Achieved results are evaluated and analysed in the conclusion.
|
|
|
Morphological Analyser Implemented as FSAs
Bezák, Jakub ; Schwarz, Petr (referee) ; Smrž, Pavel (advisor)
The aim of this paper is to introduce to its reader the field of morphemics and morphemic analysis of slovak language using morphemic analyser and to signify the difference from other world languages. In this text it is also explained the importance of finding base form of words while analysing slovak texts. Other part analyses the optimal storage of large dictionaries using finite state automata minimization. The end contains the comparison between various forms of implementation.
|
|
|
Efficient Reduction of Finite Automata
Molnárová, Veronika ; Havlena, Vojtěch (referee) ; Lengál, Ondřej (advisor)
Konečný stavový automat je matematický model popisujúci stroj vykonávajúci výpočet na zadanom vstupe cez postupnosť stavov. Za posledné storočie si tento koncept našiel využitie v rôznych odvetviach informatiky od správania postáv vo videohrách po kompilátory. Pokým automat popisuje jeden jazyk, ten môže byť reprezentovaný nekonečným množstvom rôznych automatov. Keďže veľkosť týchto automatov sa líši, pre zaistenie čo najefektívnejšej práce chceme nájsť ten najmenší z nich. V tejto práci sa pozrieme na päť rôznych typov redukcie automatov. Najskôr sa budeme zaoberať troma známymi redukčnými algoritmami, menovite to bude minimalizácia deterministického automatu, redukcia pomocou relácie simuláciu a redukcia pomocou prevodu na kanonický reziduálny automat. Tieto redukcie boli implementované v jazyku C++ a otestované na skúšobnom vzorku automatov pre porovnanie výsledkov jednotlivých redukcií. Posledne sme sa pozreli na možnosť redukovať konečný stavový automat pomocou SAT a QBF solverov. Vytvorili sme množinu pravidiel pre každý solver pre tvorbu klauzule v konjunktnej normálnej forme, ktorá dokáže jednoznačne reprezentovať automat v Booleovej algebre. S využitím tohto faktu sme vytvorili nový spôsob redukcie nedeterministického automatu.
|
|
|
Library for Finite Automata and Transducers
Bieliková, Michaela ; Lengál, Ondřej (referee) ; Hruška, Martin (advisor)
Finite state automata are widely used in the field of computer science such as formal verification, system modelling, and natural language processing. However, the models representing the reality are complicated and can be defined upon big alphabets, or even infinite alphabets, and thus contain a lot of transitions. In these cases, using classical finite state automata is not very efficient. Symbolic automata are more concise by employing predicates as transition labels. Finite state transducers also have a wide range of application such as linguistics or formal verification. Symbolic transducers replace classic transition labels with two predicates, one for input symbols and one for output symbols. The goal of this thesis is to design a library for letter and symbolic automata and transducers which will be suitable for fast prototyping.
|
|
|
Gaze-Based Keyboard
Sznapka, Jakub ; Herout, Adam (referee) ; Hradiš, Michal (advisor)
The goal of this bachelor's thesis is to create a tool for gaze typing. It deals with gaze tracking and evalution issues. It contains a description of the Swype method which is used for typing on touch screen devices. Then follows the analysis of different ways which could be used to model the language used by model. The main part is dedicated to design of the gaze typing tool and implementation using the Kaldi toolkit.
|
|
|
Morphological Analyser Implemented as FSAs
Bezák, Jakub ; Schwarz, Petr (referee) ; Smrž, Pavel (advisor)
The aim of this paper is to introduce to its reader the field of morphemics and morphemic analysis of slovak language using morphemic analyser and to signify the difference from other world languages. In this text it is also explained the importance of finding base form of words while analysing slovak texts. Other part analyses the optimal storage of large dictionaries using finite state automata minimization. The end contains the comparison between various forms of implementation.
|
|
|
Automatic Generator of Diacritics
Veselý, Lukáš ; Sumec, Stanislav (referee) ; Smrž, Pavel (advisor)
The goal of this diploma work is the suggestion and the implementation of the application, which allows adding / removing of diacritics into / from Czech written text. Retrieval "trie" structure is described along with its relation to finite state automata. Further, algorithm for minimization of finite state automata is described and various methods for adding diacritics are discussed. In practical part the implementation in Java programming language with usage of object-oriented approach is given. Achieved results are evaluated and analysed in the conclusion.
|
guest ::
