|
|
Zpětná extrakce Stateflow diagramu z kódu v jazyce C
Gavenda, Daniel ; Smrčka, Aleš (referee) ; Fiedor, Jan (advisor)
Simulink diagrams are widely used in industry, where they are used to specify control systems. The specific block used in them is the Stateflow diagram. The specified systems are often critical from the point of view of security, therefore the question of the correctness of the implementation of these systems is important. In this work, we will focus on the design, description and creation of a tool for the reverse reconstruction of the Stateflow diagram from the optimized code in the C language in order to prove the functional equivalence between the model and its corresponding code. Next, a created set of models representing models with Stateflow diagrams and codes generated from them is created, using several optimizations. The created tool will be tested on this set, it can also be used to evaluate other Stateflow analyzes and/or C code.
|
|
|
Finding Weaknesses of Hyperscan
Hrabovský, Jiří ; Vojnar, Tomáš (referee) ; Síč, Juraj (advisor)
Cilem této bakalářské práce je vysvětlit, jak funguje open source vyhledávač regulárních výrazů Hyperscan, a poskytnutí přehledu algoritmů, které interně používá. Druhým cílem je pomocí experimentů zjistit, jak moc lze ovlivnit výkon Hyperscanu skenovaným textem. Na základě zdrojového kódu a článků od autorů Hyperscanu je v kapitole 3 vysvětleno, jak Hyperscan vyhledává regulární výrazy v textu a v kapitole 4 jsou vysvětleny implementace konečných automatů používaných Hyperscanem. Různé způsoby zpomalení vyhledávačů regulárních výrazů jsou zhodnoceny a je zvolena metoda, která je založena na fungování jedné z implementací konečných automatů používaných v Hyperscanu. Na základě zvolené metody je implementován generátor, který pro vybraný výraz vygeneruje text, jehož skenování by mělo Hyperscanu zabrat výrazně déle než u normálního textu. Provedené benchmarky ukázaly, že pro některé regulární výrazy způsobil generovaný text v porovnání vůči náhodnému textu výrazné prodloužení vyhledávání Hyperscanem. U nejvíce ovlivněného regulárního výrazu trvalo skenování generovaného textu více než 8000krát déle než skenování náhodného textu.
|
|
|
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.
|
guest ::
