Algebra Seminar talk
2026-12-04
Erkko Lehtonen
On the cardinalities of clonoid lattices of Boolean functions
Abstract:
We provide a brief introduction to the theory of clones, minions, and
clonoids, which are sets of functions of several arguments with certain
closure conditions defined in terms of function class composition. These
notions arise in a natural way in universal algebra and they have proved
useful in the analysis of computational complexity of constraint
satisfaction problems. Our primary focus is on clonoids of Boolean
functions, and we present classifications of clonoids in the spirit of
Post's classification of clones. Moreover, we propose refinements and
strengthenings to Sparks's theorem on the cardinalities of clonoid lattices.