|
|
A Library for Binary Decision Diagrams
Janků, Petr ; Hrubý, Martin (referee) ; Holík, Lukáš (advisor)
Efficient manipulation of Boolean functions is an important component of many computer-aided design task. As a data structure for representing and manipulating Boolean functions, Binary Decision Diagrams are commonly used. These diagrams are commonly used in many fields such as model checking, system verification, circuit design, etc. In this thesis we describe these diagrams and there are present their modifications. Furthermore, this paper present and describes techniques for effective handling and representation of binary decision diagrams. This thesis describes the design and implementation of library that will work with these diagrams. It is further discussed how the developed library can be used within the library VATA for manipulating tree automata. Finally, the library was compared with well known and heavily optimized library CUDD, which is public and with library CacBDD. The experimental results showed that the performance of the proposed library is quite close to that of CUDD a CacBDD (has comparable and mostly even slightly better performance).
|
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor) ; Kučera, Petr (referee)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Boolean methods in knowledge compilation
Kaleyski, Nikolay Stoyanov ; Čepek, Ondřej (advisor) ; Gregor, Petr (referee)
The open problem in knowledge compilation of whether the language PI is at least as succinct as MODS is answered in the negative. For this purpose a class of Boolean functions with a number of prime implicants that is superpolynomial in their number of false points is constructed. A lower bound (proving that PI is not at least as succinct as MODS), an upper bound (proving that the counterexample cannot yield an exponential separation of PI and MODS) and the precise number of the prime implicants of these functions is computed. Powered by TCPDF (www.tcpdf.org)
|
|
|
Properties of interval Boolean functions
Hušek, Radek ; Čepek, Ondřej (advisor)
Boolean function f is k-interval if - input vector viewed as n-bit number - f is true for and only for inputs from given (at most) k intervals. Recognition of k-interval fuction given its DNF representation is coNP-hard problem. This thesis shows that for DNFs from a given solvable class (class C of DNFs is solvable if we can for any DNF F ∈ C decide F ≡ 1 in polynomial time and C is closed under partial assignment) and fixed k we can decide whether F represents k-interval function in polynomial time. 1
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (advisor)
Title: Boolean techniques in Knowledge representation Author: Miloš Chromý Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Ondřej Čepek, Ph.D., Department of Theoretical Com- puter Science and Mathematical Logic Abstract: In this thesis we will investigate switch-list representations of Boolean function and we will explore the biclique satisfiable formulas. Given a truth table representation of a Boolean function f the switch-list rep- resentation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. We include this type of representation in the Knowledge Compilation Map [Dar- wiche and Marquis, 2002] and argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard repre- sentations (such as CNF, DNF, and OBDD) with respect to their relative suc- cinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incom- parability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (advisor)
Title: Boolean techniques in Knowledge representation Author: Miloš Chromý Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Ondřej Čepek, Ph.D., Department of Theoretical Com- puter Science and Mathematical Logic Abstract: In this thesis we will investigate switch-list representations of Boolean function and we will explore the biclique satisfiable formulas. Given a truth table representation of a Boolean function f the switch-list rep- resentation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. We include this type of representation in the Knowledge Compilation Map [Dar- wiche and Marquis, 2002] and argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard repre- sentations (such as CNF, DNF, and OBDD) with respect to their relative suc- cinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incom- parability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between...
|
|
|
Boolean techniques in Knowledge representation
Chromý, Miloš ; Čepek, Ondřej (advisor) ; Mengel, Stefan (referee) ; Kofroň, Jan (referee)
Title: Boolean techniques in Knowledge representation Author: Miloš Chromý Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Doc. RNDr. Ondřej Čepek, Ph.D., Department of Theoretical Com- puter Science and Mathematical Logic Abstract: In this thesis we will investigate switch-list representations of Boolean function and we will explore the biclique satisfiable formulas. Given a truth table representation of a Boolean function f the switch-list rep- resentation of f is a list of Boolean vectors from the truth table which have a different function value than the preceding Boolean vector in the truth table. We include this type of representation in the Knowledge Compilation Map [Dar- wiche and Marquis, 2002] and argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard repre- sentations (such as CNF, DNF, and OBDD) with respect to their relative suc- cinctness. As a by-product of this analysis we also give a short proof of a long standing open question from [Darwiche and Marquis, 2002], namely the incom- parability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between...
|
|
|
Logic circuits as models of computation
Naumenko, Mykhailo ; Kazda, Alexandr (advisor) ; Kompatscher, Michael (referee)
This work focuses on the study of logic circuits. We investigated the basics of the theory of logic circuits following the textbook "Models of Computation" by John E. Savage and we used this knowledge to solve some of the examples and problems suggested in the textbook. In this work, you can find key concepts related to logical circuits. Our main topic is the estimation of the lower bounds of the circuit size and formula size of general Boolean function. We constructed simple examples of some known circuits and showed how the circuit designs may be offered. 1
|
|
|
On a matrix approach for constructing quadratic almost perfect nonlinear functions
Rezková, Zuzana ; Göloglu, Faruk (advisor) ; Žemlička, Jan (referee)
Search for new APN functions is an important topic in symmetric cryptography. The matrix approach for constructing quadratic APN functions was described by Y. Yu, M. Wang and Y. Li in 2014. The approach takes advantage of the one to one correspondence between quadratic homogenous APN functions and quadratic APN matrices. The aim of this thesis is to explain the matrices used in the original paper and show that similar matrices can be constructed directly from the algebraic normal form of the APN function. In Chapter 2 we introduce the original method adding extra theorems and expanding the proofs for better understanding. In Chapter 3 we define the matrices obtained simply from the algebraic normal form. In Chapter 4 we give examples of the matrices for chosen APN functions and show how they are related. 1
|
|
|
Generalized integral property
Hrúzová, Jana ; Žemlička, Jan (advisor) ; Příhoda, Pavel (referee)
This thesis is based on an article C. Boura and A. Canteaut, Another View of the Division Property, which is focused on division property of sets from Fn 2 . In this thesis we introduce important definitions and propositions about boolean function, polynomials and Reed-Muller codes at the beginning. Then we define parity set of a set from Fn 2 , which helps us to simplify the division property. We also show how sets, which satisfy division property of certain order, look like. From that we could follow how the division property propagate through the substitution-permutation network. 1
|
guest ::
