|
|
CSP over oriented trees
Tatarko, William ; Bulín, Jakub (advisor) ; Barto, Libor (referee)
In this thesis we present an oriented tree with only 26 vertices, whose CSP is NP-complete. This serves as a counterexample for a conjecture that any oriented tree with this property has at least 39 vertices. The work itself is divided into three chapters. In the first one, basic definitions and tools of this topic are introduced. Then, tractability of trees of special shapes is shown. Finally, NP-completeness of a certain oriented tree is proven. 1
|
|
|
Finitely generated clones
Draganov, Ondřej ; Barto, Libor (advisor) ; Bulín, Jakub (referee)
A clone is a set of finitary operations closed under composition and contain- ing all projections. We say it is finitely generated if there exist a finite subset {f1, . . . , fn} such that all the other operations can be expressed as compositions of f1, . . . , fn. We present examples of finitely and non-finitely genreated clones on finite sets. First, we demonstrate an explicit construction of operations in finitely generated clones. Secondly, we define relations such that the clones of compatible operations have restricted essential arity, and discuss several modifi- cations. Lastly, for every binary operation f which cannot be composed to yield an essentially ternary operation, we find a maximal clone of essentially at most binary operations containing f. 1
|
|
|
Weighted Clones
Gaysin, Azza ; Barto, Libor (advisor) ; Příhoda, Pavel (referee)
Weighted clones Azza Gaysin January 3, 2018 Abstract In this thesis we fully describe the structure of all binary parts of weighted clones over the Boolean clones generated by one of the semilattice operations and one or two of the constant operations. We also give a complete description of all atomic and maximal weighted clones over these clones. Keywords: Relational clones, VCSP, Weighted clones 1
|
|
|
Finitely Related Algebras
Goldstein, Marek ; Barto, Libor (advisor) ; Stanovský, David (referee)
An algebraic structure is finitely related if its clone is determined by a finite set of finitary relations. In this thesis we examine graph algebras in order to determine which of them have this property. We provide a brief sum- mary of a background theory and we present an overview of known results, in particular, we emphasize the relation between finitely related algebras and Mal'cev conditions. Further we present basic results about the structure of graph algebras. The main part of this thesis is a partial classification of finitely related graph algebras. We provide proofs for various classes of graph algebras, for example for algebras defined by connected bipartite graphs or algebras de- fined by graphs containing certain subgraphs, although several cases are missing to complete the classification. 1
|
|
|
The arity of NU polymorphisms
Draganov, Ondřej ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
This paper deals with an arity of NU polymorphisms of relational structures. The goal is to simplify and clearly describe an already existing example of a relational structure, which has an NU polymorphism, but no NU polymorphisms of low arity in respect to arity of relations and to a number of elements in the relational structure. We explicitly describe m-ary relational structures with n elements, n ≥ 2, m ≥ 3, which have no NU polymorphisms of arity (m − 1)2n−2 , but have an NU polymorphism of arity (m − 1)2n−2 + 1, which is constructed in the paper, and binary relational structures with n elements, n ≥ 3, which have no NU polymorphisms of arity 22n−3 , but have an NU polymorphism of arity 22n−3 + 1.
|
|
|
Relational Approach to Universal Algebra
Opršal, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Mayr, Peter (referee)
Title: Relational Approach to Universal Algebra Author: Jakub Opršal Department: Department of Algebra Supervisor: doc. Libor Barto, Ph.D., Department of Algebra Abstract: We give some descriptions of certain algebraic properties using rela- tions and relational structures. In the first part, we focus on Neumann's lattice of interpretability types of varieties. First, we prove a characterization of vari- eties defined by linear identities, and we prove that some conditions cannot be characterized by linear identities. Next, we provide a partial result on Taylor's modularity conjecture, and we discuss several related problems. Namely, we show that the interpretability join of two idempotent varieties that are not congruence modular is not congruence modular either, and the analogue for idempotent va- rieties with a cube term. In the second part, we give a relational description of higher commutator operators, which were introduced by Bulatov, in varieties with a Mal'cev term. Furthermore, we use this result to prove that for every algebra with a Mal'cev term there exists a largest clone containing the Mal'cev operation and having the same congruence lattice and the same higher commu- tator operators as the original algebra, and to describe explicit (though infinite) set of identities describing supernilpotence...
|
|
|
Varieties of superalgebras
Lišková, Adéla ; Žemlička, Jan (advisor) ; Barto, Libor (referee)
The goal of the thesis is to introduce the basics of the theory of superalgebras, that is Z2-graded algebras over a field of characteristic different from two, as well as to present necessary basics of universal and multilinear algebra, especially the tensor product and the terms variety of algebra and ideal of identities. We present the definitions of algebra and superalgebra including examples, we then look into the tensor product of superalgebras and its properties, Clifford and Grassmann superalgebras. A part of the thesis is dedicated to the construction of the free nonassociative algebra and the clarification of the relationship between varieties of algebras and ideals of identities including the specification of said relationship for superalgebras. The thesis also deals with varieties of superalgebras. 1
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Bulatov, Andrei (referee)
Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele- vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a by-product, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for so-called special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.
|
|
|
Vážené klony
Vančura, Jiří ; Barto, Libor (advisor) ; Příhoda, Pavel (referee)
The well know constraint satisfaction problem (CSP) can be generalized to a class of optimization problems - VCSP. In 2012, D. A. Cohen, M. C. Cooper, P. Creed, P. G. Jeavons and S. Živný proved that weighted clones and weighted relational clones play the same role for the VCSP as do clones and relational clones for the CSP. However the structure of weighted clones remains unknown even for two element domain. This thesis presents a more detailed proof of the result mentioned above and then it investigates the structure of weighted clones. For Boolean domain, we present a complete classification of weighted clones over all seven minimal clones. Powered by TCPDF (www.tcpdf.org)
|
|
|
How Google works
Vaněček, Jaromír ; Tůma, Jiří (advisor) ; Barto, Libor (referee)
This thesis deals with the web search engine Google, particularly the way how searched pages are ordered and with the application of this process in different areas. First, we briefly introduce how a web search engine works, create the Google matrix and show principle of the PageRank algorithm. Then, in the completely mathematical section of the work, we describe the mathematical theory supporting our statements including Perron's theorem. The next section is concerned with how to use PageRank to compare teams in football Synot league. In the end few simple observations on how different facts in the web's hyperlink structure influence the Google matrix will be described. Powered by TCPDF (www.tcpdf.org)
|
guest ::
