Název:
Konečně generované klony
Překlad názvu:
Finitely generated clones
Autoři:
Draganov, Ondřej ; Barto, Libor (vedoucí práce) ; Bulín, Jakub (oponent) Typ dokumentu: Diplomové práce
Rok:
2018
Jazyk:
eng
Abstrakt: [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
Klíčová slova:
esenciální proměnné; klon; konečně generovaný; nekonečně generovaný; clone; essential variables; finitely generated; non-finitely generated