Original title:
Konečně generované klony
Translated title:
Finitely generated clones
Authors:
Draganov, Ondřej ; Barto, Libor (advisor) ; Bulín, Jakub (referee) Document type: Master’s theses
Year:
2018
Language:
eng Abstract:
[eng][cze] 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. 1Klonem rozumíme množinu operací konečné arity, která je uzavřená na sklá- dání a obsahuje projekce. Řekneme, že je konečně generovaný, existuje-li konečná podmnožina {f1, . . . , fn} taková, že všechny ostatní operace lze vyjádřit pomocí skládání f1, . . . , fn. Práce představuje příklady konečně a nekonečně generova- ných klonů na konečné množině. Nejprve ukážeme explicitní konstrukci, pomocí které můžeme najít generátory některých konečně generovaných klonů, a expli- citní vyjádření všech operací těchto klonů jako termy nalezených generátorů. Dále definujeme relace, jejichž kompatibilní operace mají omezenou esenciální aritu, a diskutujeme jejich možné modifikace. Konečně pro každou binární operaci f, pomocí které nelze naskládat esenciálně ternární operaci, nalezneme maximální klon esenciálně binárních operací, který f obsahuje. 1
Keywords:
clone; essential variables; finitely generated; non-finitely generated; esenciální proměnné; klon; konečně generovaný; nekonečně generovaný
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/99304