|
|
Generic Template-Based Synthesis of Program Abstractions
Marušák, Matej ; Holík, Lukáš (referee) ; Malík, Viktor (advisor)
Cieľom tejto práce je návrh a implementácia generického strategy solveru pre nástroj 2LS. 2LS je analyzátor na statickú verifikáciu programov napísaných v jazyku C. Verifikovaný program je za využita abstraktnej interpretácie analyzovaný SMT solverom. Prevod z ab- straktného stavu programu do logickej formule, s ktorou vie pracovať SMT solver vykonáva komponenta nazývaná strategy solver. Aktuálne pre každú doménu existuje jeden takýto solver. Navrhované riešenie vytvára jeden obecný strategy solver, ktorý zjednodušuje tvorbu nových domén. Zároveň navrhovaný spôsob umožnuje prevedenie existujúcich domén a teda zmenšuje program analyzátora.
|
|
|
Generating Structured Test Data
Olšák, Ondřej ; Holík, Lukáš (referee) ; Smrčka, Aleš (advisor)
The goal of the bachelor's thesis is to create a tool for generating files with structure data content. The purpose of these files is to be used as test data conforming to testing of program input space. This thesis focuses on tree-structured data. The tool integrates tools implemented previously within Testos framework for generating test data in order to satisfy user-defined coverage criterion. The tool is able to generate a set of files in JSON or XML format containing test data satisfying ECC, BCC, or PWC coverage criterion.
|
|
|
Incremental Inductive Coverability for Alternating Finite Automata
Vargovčík, Pavol ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
In this work, we propose a specialization of the inductive incremental coverability algorithm that solves alternating finite automata emptiness problem. We experiment with various design decisions, analyze them and prove their correctness. Even though the problem itself is PSpace-complete, we are focusing on making the decision of emptiness computationally feasible for some practical classes of applications. We have obtained interesting comparative results against state-of-the-art algorithms, especially in comparison with antichain-based algorithms.
|
|
|
Entrepreneurial Project
Holík, Lukáš ; Smolíková,, Lenka (referee) ; Heralecký, Tomáš (advisor)
The goal of this dissertation is to create a business plan for mr. David Mokrý - owner of café Blue Queen in Boskovice. In a short time he would like to make his business bigger and found another café - pub (Black King).The needed data for creating a project of new successful cafe, which should become the most popular in selected location, I'm going to get by many market analyses, respective by analyses of internal and external neighborhood.
|
|
|
Congruences for Tree Automata
Žufan, Petr ; Janků, Petr (referee) ; Holík, Lukáš (advisor)
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.
|
|
|
Simulation for Symbolic Automata
Síč, Juraj ; Lengál, Ondřej (referee) ; Holík, Lukáš (advisor)
Symbolic automata are similar to classical automata with one big difference: transitions are labelled with predicates defined in separate logical theory. This allows usage of large alphabets while taking less space. In this work we are interested in computing simulation (a binary relation on states that language inclusion) for these automata. This can be then used for reducing the size of automata without the need to determinize them first. There exist few algorithms for computing simulation over Kripke structures, which were then altered to work over labeled transition systems and classical automata. We show how one of these algorithms can be modified for symbolic automata by using the partition of the alphabet domain that is compatible with the predicates labelling transitions and by using the possibilities of the alphabet theory.
|
|
|
Arithmetical completeness of the logic R
Holík, Lukáš ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
The aim of this work is to use contemporary notation to build theory of Rosser logic, explain in detail its relation to Peano arithmetic, show its Kripke semantics and finally using plural self-reference show the proof of arithmetical completeness. In the last chapter we show some of the properties of Rosser sentences. Powered by TCPDF (www.tcpdf.org)
|
|
|
Towards Static Analysis of Languages with Dynamic Features
Hauzar, David ; Plášil, František (advisor) ; Sinz, Carsten (referee) ; Holík, Lukáš (referee)
Dynamic features of programming languages such as dynamic type system, dynamic method calls, dynamic code execution, and dynamic data structures provide the flexibility which can accelerate the development, but on the other hand they reduce the information that is checked at compile time and thus make programs more error-prone and less efficient. While the problem of lacking compile time checks can be partially addressed by techniques of static analysis, dynamic features pose major challenges for these techniques sacrificing their precision, soundness, and scalability. To tackle this problem, we propose a framework for static analysis that automatically resolves these features and thus allows defining sound and precise static analyses similarly as the analyzed program would not use these functions. To build the framework, we propose a novel heap analysis that models associative arrays and dynamic (prototype) objects. Next, we propose value analysis providing additional information necessary to resolve dynamic features. Finally, we propose a technique that automatically and generically combines value analysis and a heap analysis modeling associative arrays and prototype objects. Powered by TCPDF (www.tcpdf.org)
|
|
|
Ultrapower construction in set theory
Holík, Lukáš ; Honzík, Radek (advisor) ; Verner, Jonathan (referee)
The presented work contains the history of origin of measure, its connection with measurable cardinals and summary of all elementary definitions and no- tions needed for the generalization of ultrapower construction in model theory for proper classes. One of the parts of the presented theory is the proof of el- ementary properties needed for the application of ultrapower construction to measurable cardinals. Using all previous results we prove the Theorem of Dana Scott about the connection between existence of a measurable cardinal and the size of the universe.
|
|
|
Simulace a protiřetězce pro efektivní práci s konečnými automaty
Holík, Lukáš ; Černá, Ivana (referee) ; Jančar, Petr (referee) ; Vojnar, Tomáš (advisor)
Cílem této práce je vývoj technik umožňujících praktické využití nedeterministických konečných automatů, zejména nedeterministických stromových automatů. Jde zvláště o techniky pro redukci velikosti a testování jazykové inkluze, jež hrají zásadní roli v mnoha oblastech aplikace konečných automatů. V oblasti redukce velikosti vycházíme z dobře známých metod pro slovní automaty které jsou založeny na relacích simulace. Navrhli jsme efektivní algoritmy pro výpočet stromových variant simulačních relací a identifikovali jsme nový typ relace založený na kombinaci takzvaných horních a dolních simulací nad stromovými automaty. Tyto kombinované relace jsou zvláště vhodné pro redukci velikosti automatů slučováním stavů. Navržený princip kombinace relací simulace je relevantní i pro slovní automaty. Náš přínos v oblasti testování jazykové inkluze je dvojí. Nejprve jsme zobecnili na stromové automaty takzvané protiřetězcové algoritmy, které byly původně navrženy pro slovními automaty. Dále se nám podařilo použitím simulačních relací výrazně zefektivnit protiřetězcové algoritmy pro testování jazykové inkluze jak pro slovní, tak pro stromové automaty. Relevanci našich technik pro praxi jsme demonstrovali jejich nasazením v rámci regulárního stromového model checkingu, což je verifikační metoda založená na stromových automatech. Použití našich algoritmů zde vedlo k výraznému zrychlení a zvětšení škálovatelnosti celé metody. Základní myšlenky našich algoritmů pro redukci velikosti automatů a testování jazykové inkluze jsou aplikovatelné i na jiné typy automatů. Příkladem jsou naše redukční techniky pro alternující Büchiho automaty prezentované v poslední části práce.
|
guest ::
RSS feed.