On the lattice of multi-sorted relational clones on a two-element domain
| Název práce v češtině: | O svazu multisortových relačních klonů na dvouprvkové množině |
|---|---|
| Název v anglickém jazyce: | On the lattice of multi-sorted relational clones on a two-element domain |
| Klíčová slova: | relační klon|klon|Galoisova korespondence|svaz klonů |
| Klíčová slova anglicky: | Relational clone|clone|Galois connection|lattice of clones |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | Dmitrii Zhuk, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 20.11.2023 |
| Datum zadání: | 21.11.2023 |
| Datum potvrzení stud. oddělením: | 26.11.2023 |
| Datum a čas obhajoby: | 19.06.2024 08:00 |
| Datum odevzdání elektronické podoby: | 09.05.2024 |
| Datum odevzdání tištěné podoby: | 09.05.2024 |
| Datum proběhlé obhajoby: | 19.06.2024 |
| Oponenti: | doc. Mgr. Libor Barto, Ph.D. |
| Zásady pro vypracování |
| The goal of the thesis is to describe and understand multi-sorted relational clones on a two-element domain. Start with usual predicates having just one sort of variables.
Consider predicates on a 2-element domain definable by disjunctions of linear equations. Define elementary operations on these predicates that cover the closure under primitive positive formulas. Find all sets of predicates closed under these elementary operations. Prove that any predicate can be represented using disjunctions of linear equations. Try to generalize the obtained results for two-sorted and multi-sorted predicates. Find the cardinality and some properties of the lattices of such closed sets. |
| Seznam odborné literatury |
| Kerkhoff, Sebastian, Reinhard Pöschel, and Friedrich Martin Schneider. "A short introduction to clones." Electronic Notes in Theoretical Computer Science 303 (2014): 107-120.
Lau, Dietlinde. Function algebras on finite sets: Basic course on many-valued logic and clone theory. Springer Science & Business Media, 2006. Zhuk, Dmitriy N. "Key (critical) relations preserved by a weak near-unanimity function." Algebra universalis 77.2 (2017): 191-235. Barto, Libor, Andrei Krokhin, and Ross Willard. "Polymorphisms, and how to use them." Dagstuhl Follow-Ups. Vol. 7. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. |
| Předběžná náplň práce v anglickém jazyce |
| Consider predicates on a two-element domain definable as disjunctions of equalities x=a (denote DE) and the predicates definable as disjunctions linear equations modulo 2 (denote DL). Define elementary operations on such predicates including permutation of variables, identification of variables, adding a dummy variable, composition of predicates.
1) Find all sets of predicates from DE closed under elementary operations 2) Find all sets of predicates from DL closed under elementary operations 3) Compare the result in 2 with the Post Lattice. 4) Compare the closure under elementary operations and the closure under primitive positive formulas, i.e., formulas with existential quantifiers and conjunctions. 5) Find a representation of any relation as a conjunction of predicates from DL that can be derived from it. 6) Find the cardinality of the lattice of two-sorted relational clones on a two-element domain, i.e., closed sets of predicates on a two-element domain having variables of 2 sorts. 7) Generalize to the k-sorted case. 8) Describe all two-sorted relational clones on a two-element domain. Thus, the main goal is to describe all two-sorted relational clones on a two-element domain, and therefore (by the Galois Connection) describe all clones of vector-functions (f_1,f_2), where f_1 and f_2 are Boolean functions of the same arity and the composition is applied coordinate-wise. |