On the lattice of multi-sorted relational clones on a two-element domain
| Thesis title in Czech: | O svazu multisortových relačních klonů na dvouprvkové množině |
|---|---|
| Thesis title in English: | On the lattice of multi-sorted relational clones on a two-element domain |
| Key words: | relační klon|klon|Galoisova korespondence|svaz klonů |
| English key words: | Relational clone|clone|Galois connection|lattice of clones |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | Dmitrii Zhuk, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 20.11.2023 |
| Date of assignment: | 21.11.2023 |
| Confirmed by Study dept. on: | 26.11.2023 |
| Date and time of defence: | 19.06.2024 08:00 |
| Date of electronic submission: | 09.05.2024 |
| Date of submission of printed version: | 09.05.2024 |
| Date of proceeded defence: | 19.06.2024 |
| Opponents: | doc. Mgr. Libor Barto, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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. |
| Preliminary scope of work in English |
| 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. |