=Paper=
{{Paper
|id=Vol-2925/short2
|storemode=property
|title=Linearly definable classes of Boolean functions
|pdfUrl=https://ceur-ws.org/Vol-2925/short2.pdf
|volume=Vol-2925
|authors=Miguel Couceiro,Erkko Lehtonen
|dblpUrl=https://dblp.org/rec/conf/algos/CouceiroL20
}}
==Linearly definable classes of Boolean functions
==
https://ceur-ws.org/Vol-2925/short2.pdf
L INEARLY DEFINABLE CLASSES OF B OOLEAN FUNCTIONS⇤
Miguel Couceiro Erkko Lehtonen
Université de Lorraine, CNRS, Inria, LORIA Centro de Matemática e Aplicações
F-54000 Nancy, France Faculdade de Ciências e Tecnologia
Universidade Nova de Lisboa, Portugal
Dedicated to Maurice Pouzet on the occasion of his 75th birthday
A BSTRACT
In this paper we address the question “How many properties of Boolean functions can be defined by
means of linear equations?” It follows from a result by Sparks that there are countably many such
linearly definable classes of Boolean functions. In this paper, we refine this result by completely
describing these classes. This work is tightly related with the theory of function minors and stable
classes, a topic that has been widely investigated in recent years by several authors including Maurice
Pouzet.
Keywords Functional equation · linear definability · clone · clonoid · Boolean function
1 Introduction and motivation
Functional equations are universally quantified first-order sentences in a certain algebraic syntax, with a single function
symbol and no other predicate symbol than equality. More precisely, a functional equation for a function of several
arguments from A to B is a formal expression
h1 (f (g1 (v1 , . . . , vp )), . . . , f (gm (v1 , . . . , vp ))) = h2 (f (g10 (v1 , . . . , vp )), . . . , f (gt0 (v1 , . . . , vp ))), (1)
where m, t, p 1, h1 : B m ! C, h2 : B t ! C, each gi and gj0 is a map Ap ! A, the v1 , . . . , vp are p distinct
symbols called vector variables, and f is a distinct symbol called function symbol. An n-ary function f : An ! B is
said to satisfy the equation (1) if, for all a1 , . . . , ap 2 An , we have
h1 (f (g1 (a1 , . . . , ap )), . . . , f (gm (a1 , . . . , ap ))) = h2 (f (g10 (a1 , . . . , ap )), . . . , f (gt0 (a1 , . . . , ap ))),
where the gi and gi0 are applied componentwise. Well-known examples of functional properties definable by such
functional equations include the linearity property of functions over fields, the monotonicity and convexity properties
that are typically expressed by functional inequalities.
Such functional equations regained interest in 2000, due to the work of Ekin, Foldes, Hammer, and Hellerstein [8] who
showed that the equational classes of Boolean functions are exactly those classes that are closed under introduction
of fictitious variables, and identification and permutation of variables. These operations on functions give rise to a
preorder on functions, the so-called simple minor relation, and equational classes are exactly the “initial segments”
for this preorder [3, 7]. Alternatively, these classes appear naturally in a Galois theory proposed by Pippenger [18]
that is based on the preservation relation between functions and relation pairs (also called “relational constraints”).
Using this framework it was shown that, even in the case of Boolean functions, there are uncountably many classes of
functions definable by functional equations. For instance, all Post’s classes (clones of Boolean functions), traditionally
characterized by relations, are definable by functional equations.
⇤
This work is funded by National Funds through the FCT – Fundação para a Ciência e a Tecnologia, I.P., under the scope of the
project UIDB/00297/2020 (Center for Mathematics and Applications).
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
This motivated several studies that considered syntactic restrictions on functional equations and relational constraints.
Foldes and Pogosyan [10] considered a variant, the so-called functional terms, to define all Boolean clones and to give a
criterion to determine whether a clone is finitely definable. In [4] the authors focused on linear equations and showed
that the classes of Boolean functions definable by linear equations are exactly those that are stable under left and right
compositions with the clone of constant-preserving linear functions or, equivalently, definable by affine constraints.
This was later extended to arbitrary functions over fields [5], and to stability under compositions with arbitrary clones
[6]: an equational class is definable by relation pairs in which the two relations are invariant for clones C1 and C2 ,
respectively, if and only if the class is stable under left composition with C1 and under right composition with C2 (in
short, (C1 , C2 )-stable). Instances of the idea of (C1 , C2 )-stability are present in various studies. The initial segments
of so-called C-minor quasiorders, systematically studied in [12, 13, 14, 15, 16, 17], are exactly such (C1 , C2 )-stable
classes where the first clone C1 is the clone of projections. On the other hand, when C2 is the clone of projections,
we get clonoids, as studied by Aichinger, Mayr, and others [1, 2, 21]. The case when both C1 and C2 are clones of
projections corresponds to minor-closed classes. As an example of recent work on (C1 , C2 )-stable classes that is
closely related with the current paper, we would like to mention studies of function classes stable under left and right
compositions with clones of linear functions by Fioravanti and Kreinecker [9, 11].
Getting back to linearly definable classes of Boolean functions, in [5] it was observed that, for each integer k 0, the
class of Boolean functions whose degree is upper bounded by k is definable by the following linear equation:
X X
f( vi ) = 0.
I✓{1,...,k+1} i2I
This shows that even in the case of Boolean functions, there are infinitely many linearly definable classes. Other
examples were also provided, but it remained until recently an open problem to determine whether there are uncountably
many linearly definable classes as is the case with classes definable by unrestricted functional equations. The answer
follows from a result of Sparks [21, Theorem 1.3], namely, there are a countably infinite number of linearly definable
classes.
In this paper we refine this result by explicitly describing the linearly definable classes of Boolean functions. After
recalling some basic notions and results on function minors and stability under composition with clones in Section 2, we
then completely describe the lattice of linearly definable classes (Section 3). Using this result and Post’s classification
of Boolean clones, we can easily determine the classes which are stable under right and left compositions with clones
C1 and C2 containing the clone of constant-preserving linear functions (Section 4).
2 Basic notions and preliminary results
Throughout this paper, let N and N+ denote the set of all nonnegative integers and the set of all positive integers,
respectively. For any n 2 N, the symbol [n] denotes the set { i 2 N | 1 i n }.
Let A and B be sets. A mapping of the form f : An ! B for some n 2 N+ is called a function of several arguments
from A to B (or simply a function). The number n is called the arity of f and denoted by ar(f ). If A = B, then such a
function is called an operation on A. We denote by FAB and OA the set of all functions of several arguments from A
(n)
to B and the set of all operations on A, respectively. For any n 2 N+ , we denote by FAB the set of all n-ary functions
(n)
in FAB , and for any C ✓ FAB , we let C (n) := C \ FAB and call it the n-ary part of C.
(n)
Example 2.1. For b 2 B and n 2 N, the n-ary constant function cb : An ! B is given by the rule (a1 , . . . , an ) 7! b
for all a1 , . . . , an 2 A.
(n)
Example 2.2. In the case when A = B, for n 2 N and i 2 [n], the i-th n-ary projection pri : An ! A is given by
the rule (a1 , . . . , an ) 7! ai for all a1 , . . . , an 2 A.
Let f : An ! B and i 2 [n]. The i-th argument is essential in f if there exist a1 , . . . , an , a0i 2 A such that
f (a1 , . . . , an ) 6= f (a1 , . . . , ai 1 , a0i , ai+1 , . . . , an ).
An argument that is not essential is fictitious.
2.1 Minors and functional composition
Let f : B n ! C and g1 , . . . , gn : Am ! B. The composition of f with g1 , . . . , gn is the function
f (g1 , . . . , gn ) : Am ! C given by the rule
f (g1 , . . . , gn )(a) := f (g1 (a), . . . , gn (a)), for all a 2 Am .
Let : [n] ! [m]. Define the function f : Am ! B by the rule
f (a1 , . . . , am ) = f (a (1) , . . . , a (n) ),
for all a1 , . . . , am 2 A. Such a function f is called a minor of f . Intuitively, minors of f are all those functions
that can be obtained from f by manipulation of its arguments: permutation of arguments, introduction of fictitious
arguments, identification of arguments. It is clear from the definition that the minor f can be obtained as a composition
of f with m-ary projections on A:
(m) (m)
f = f (pr (1) , . . . , pr (n) ).
We write f g if f is a minor of g. The minor relation is a quasiorder (a reflexive and transitive relation) on FAB ,
and it induces an equivalence relation ⌘ on FAB and a partial order on the quotient FAB /⌘ in the usual way: f ⌘ g if
f g and g f , and f /⌘ g/⌘ if f g.
Functional composition can be extended to classes of functions. Let C ✓ FBC and K ✓ FAB . The composition of C
with K is defined as
CK := { f (g1 , . . . , gn ) | f 2 C (n) , g1 , . . . , gn 2 K (m) , n, m 2 N+ }.
It follows immediately from definition that function class composition is monotone, i.e., if C, C 0 ✓ FBC and
K, K 0 ✓ FAB satisfy C ✓ C 0 and K ✓ K 0 , then CK ✓ C 0 K 0 .
2.2 Clones, minor closure and stability under compositions with clones
A class C ✓ OA is called a clone on A if CC ✓ C and C contains all projections. The set of all clones on A is a
closure system in which the greatest and least elements are the clone OA of all operations on A and the clone of all
projections on A, respectively.
Definition 2.3. Let K ✓ FAB , C1 ✓ OB , and C2 ✓ OA . We say that K is stable under left composition with C1 if
C1 K ✓ K, and that K is stable under right composition with C2 is KC2 ✓ K. If both C1 K ✓ K and KC2 ✓ K
hold, we say that K is (C1 , C2 )-stable. If K, C ✓ OA and K is (C, C)-stable, we say that K is C-stable. The set of
all (C1 , C2 )-stable subsets of FAB is a closure system.
Remark 2.4. A set K ✓ FAB is minor-closed if and only if it is stable under right composition with the set of all
projections on A. Every clone is minor-closed. A clone C is (C, C)-stable.
Lemma 2.5. Let C1 and C10 be clones on B and C2 and C20 clones on A such that C1 ✓ C10 and C2 ✓ C20 . Then for
every K ✓ FAB , it holds that if K is (C10 , C20 )-stable then K is (C1 , C2 )-stable.
Proof. Assume that K is (C10 , C20 )-stable. It follows from the monotonicity of function class composition that
C1 K ✓ C10 K ✓ K and KC2 ✓ KC20 ✓ K.
In other words, K is (C1 , C2 )-stable.
3 The lattice of linearly definable classes of Boolean functions
Recall that operations on {0, 1} are called Boolean functions. In this section we completely describe the lattice of
linearly definable classes of Boolean functions. The starting point is the following characterization of these classes first
obtained for Boolean functions in [4], and later extended to classes of functions defined on {0, 1} and valued in rings
[6].
Theorem 3.1. A class of Boolean functions is linearly definable if and only if it is stable under left and right compositions
with the clone of constant-preserving linear Boolean functions.
Hence to completely describe the linearly definable classes it suffices to determine those that are stable under left and
right compositions with the clone of constant-preserving linear Boolean functions. This will be presented in Subsection
3.2.
3.1 Some special classes of Boolean functions
The class of all Boolean functions is denoted by ⌦. It is well known that every f 2 ⌦(n) is represented by a unique
multilinear polynomial over the two-element field, i.e., a polynomial with coefficients in {0, 1} in which no variable
appears with an exponent greater than 1. This polynomial is known as the Zhegalkin polynomial of f , and it can be
written as X
f= xS ,
S2Mf
Q
where xS is a shorthand for i2S xi and P where Mf ✓ P([n]) is the family of index sets corresponding to the
monomials of f . Note that x; = 1 and S2; xS = 0. The terms xS with S 6= ; are called monomials. If ; 2 Mf ,
then we say that f has constant term 1; otherwise f has constant term 0. Without any risk of confusion, we will often
denote functions by their Zhegalkin polynomials, and we refer to the set Mf as the set of monomials of f .
The degree of a Boolean function f , denoted deg(f ), is the size of the largest monomial of f , i.e.,
deg(f ) := max |S|
S2Mf
for f 6= 0, and we agree that deg(0) := 0. For k 2 N, we denote by Dk the class of all Boolean functions of degree at
most k. Clearly Dk ( Dk+1 for all k 2 N. A Boolean function f is linear if deg(f ) 1.2 We denote by L the class of
all linear functions. Thus L = D1 .
For a 2 {0, 1}, let Ca := { f 2 ⌦ | f (0, . . . , 0) = a } and Ea := { f 2 ⌦ | f (1, . . . , 1) = a }. Clearly C0 \ C1 = ;
and C0 [ C1 = ⌦; similarly, E0 \ E1 = ; and E0 [ E1 = ⌦. It is easy to see that Ca is the class of all Boolean functions
with constant term a.
For a 2 {0, 1}, a Boolean function f is a-preserving if f (a, . . . , a) = a. A function is constant-preserving if it is
both 0- and 1-preserving. We denote the classes of all 0-preserving, of all 1-preserving, and of all constant-preserving
functions by T0 , T1 , and Tc , respectively. Note that Tc = T0 \ T1 . It follows from the definitions that T0 = C0 ,
T1 = E1 , and Tc = C0 \ E1 .
Remark 3.2. The reason why we have introduced multiple notation for the classes T0 = C0 and T1 = E1 is to facilitate
writing certain statements in a parameterized form and to make reference, as the case may be, to either the classes Ca
(a 2 {0, 1}), Ea (a 2 {0, 1}), or Ta (a 2 {0, 1}).
The parity of a Boolean function f , denoted par(f ), is a number, either 0 or 1, which is given by
par(f ) := |Mf \ {;}| mod 2.
We call a function even or odd if its parity is 0 or 1, respectively. We denote by P0 and P1 the classes of all even and of
all odd functions, respectively. Clearly P0 \ P1 = ; and P0 [ P1 = ⌦.
For a 2 {0, 1}, let a denote the negation of a, that is, a := 1 a. A function f is self-dual if
f (a1 , . . . , an ) = f (a1 , . . . , an ), for all a1 , . . . , an 2 {0, 1}.
A function f is reflexive (or self-anti-dual) if f (a1 , . . . , an ) = f (a1 , . . . , an ) for all a1 , . . . , an 2 {0, 1}. We denote
by S the class of all self-dual functions. Let Sc := S \ Tc , the class of constant-preserving self-dual functions.
We also let L0 := L \ T0 , L1 := L \ T1 , LS := L \ S, and Lc := L \ Tc . It is easy to verify that L0 = L \ C0 ,
L1 = (L \ P0 \ C1 ) [ (L \ P1 \ C0 ), Lc = L \ P1 \ C0 , and LS = L \ P1 .
It was shown by Post [19] that there are a countably infinite number of clones of Boolean functions. In this paper, we
will only need a handful of them, namely the clones ⌦, T0 , T1 , Tc , S, Sc , L, L0 , L1 , LS, and Lc that were defined above.
Let f be an n-ary Boolean function. The characteristic of a set S ✓ [n] in f is given by
ch(S, f ) := |{ A 2 Mf | S ( A }| mod 2.
The characteristic rank of f , denoted by (f ), is the smallest integer m such that ch(S, f ) = 0 for all subsets S ✓ [n]
with |S| m. Clearly, (f ) n because ch([n], f ) = 0. For k 2 N, denote by Xk the class of all Boolean functions
of characteristic rank at most k. For any k 2 N, we have Xk ( Xk+1 . The inclusion is proper, as witnessed by the
function x1 . . . xk+1 2 Xk+1 \ Xk . Moreover, for any k 2 N, we have Dk ✓ Xk .
Reflexive and self-dual functions have a beautiful characterization in terms of the characteristic rank.
Lemma 3.3 (Selezneva, Bukhman [20, Lemmata 3.1, 3.5]).
1. A Boolean function f is reflexive if and only if (f ) = 0.
2
Strictly speaking, functions of degree at most 1 are affine in the sense of linear algebra. We go along with the term linear that is
common in the context of clone theory and especially in the theory of Boolean functions.
⌦
P0 C0 E0 E1 C1 P1
C0 \ E0 C1 \ E1 C0 \ E1 C1 \ E0
Figure 1: A block of eleven Lc -stable classes.
2. A Boolean function f is self-dual if and only if f + x1 is reflexive.
3. A Boolean function f is self-dual if and only if f is odd and (f ) = 1.
In other words, X0 = X1 \ P0 is the class of all reflexive functions, X1 \ P1 is the class of all self-dual functions, and
X1 is the class of all self-dual or reflexive functions.
3.2 Lc -stable classes
We can now present the main result of the paper, namely, a complete description of the Lc -stable classes or, equivalently,
of the linearly definable classes of Boolean functions. Of particular importance is the poset of the eleven classes ⌦,
P0 , P1 , C0 , C1 , E0 , E1 , C0 \ E0 , C0 \ E1 , C1 \ C0 , C1 \ E1 that is shown in Figure 1. It is noteworthy that the four
minimal classes of this poset are pairwise disjoint, and that the six lower covers of ⌦ are precisely the unions of the six
different pairs of minimal classes.
Theorem 3.4. The Lc -stable classes are
⌦, Ca , Ea , Pa , Ca \ Eb ,
Dk , Dk \ Ca , Dk \ Ea , Dk \ P a , Dk \ Ca \ Eb ,
Xk , Xk \ Ca , X k \ Ea , Xk \ Pa , Xk \ Ca \ Eb ,
Di \ X j , Di \ Xj \ Ca , Di \ X j \ Ea , Di \ X j \ P a , Di \ Xj \ Ca \ Eb ,
D0 , D0 \ Ca , ;,
for a, b 2 {0, 1} and i, j, k 2 N+ with i > j 1.
The lattice of Lc -stable classes is shown in Figure 2. In order to avoid clutter, we have used some shorthand notation.
The diagram includes multiple copies of the 11-element poset of Figure 1 (the shaded blocks) connected by thick triple
lines. Each thick triple line between a pair of such blocks represents eleven edges, each connecting a vertex of one
poset to its corresponding vertex in the other poset. We have labeled in the diagram the meet-irreducible classes, as well
as a few other classes of interest; the remaining classes are intersections of the meet-irreducible ones.
The proof of Theorem 3.4 is omitted for space constraints. The proof has two parts. First we need to verify that the
classes listed in Theorem 3.4 are Lc -stable. Since intersections of Lc -stable classes are Lc -stable, it suffices to show
this for the meet-irreducible classes; this is rather straightforward. Secondly, we need to verify that there are no other
Lc -stable classes. This is a more difficult task and can be accomplished by proving that each class K is generated by
any subset of K that contains for each proper subclass C of K an element in K \ C.
4 Stability under clones containing Lc
Using Theorem 3.4 together with Lemma 2.5 it is straightforward to determine the (C1 , C2 )-stable classes for any
clones C1 and C2 containing Lc . Such classes must occur among the Lc -stable classes by Lemma 2.5, so it is just a
matter of deciding which ones are (C1 , C2 )-stable. In particular, we obtain the C-stable classes for every clone C
containing Lc , i.e., the clones ⌦, T0 , T1 , Tc , S, Sc , L, L0 , L1 , LS and Lc .
⌦
P0 C0 E0 E1 C1 P1
Tc
X4
X3
D4
X2
D 4 \ X3
X1
X0 S
D3 D 4 \ X2
Sc
D 3 \ X2 D 4 \ X1
D2 D 3 \ X1
D 2 \ X1
D1
L0 L1 LS
Lc
D0
;
Figure 2: Lc -stable classes.
Theorem 4.1.
(i) The Lc -stable classes are ⌦, Ca , Ea , Pa , Ca \ Eb , Dk , Dk \ Ca , Dk \ Ea , Dk \ Pa , Dk \ Ca \ Eb , Xk , Xk \ Ca ,
Xk \ Ea , Xk \ Pa , Xk \ Ca \ Eb , Di \ Xj , Di \ Xj \ Ca , Di \ Xj \ Ea , Di \ Xj \ Pa , Di \ Xj \ Ca \ Eb ,
D0 , D0 \ Ca , ;, for a, b 2 {0, 1} and i, j, k 2 N+ with i > j 1.
(ii) The LS-stable classes are ⌦, Xk , X1 \ Pa , Dk , D1 \ Pa , Di \ Xj , Di \ X1 \ Pa , D0 , ;, for a 2 {0, 1} and
i, j, k 2 N+ with i > j 1.
(iii) The L0 -stable classes are ⌦, C0 , Dk , Dk \ C0 , D0 , D0 \ C0 , ;, for k 2 N+ .
(iv) The L1 -stable classes are ⌦, E1 , Dk , Dk \ E1 , D0 , D0 \ C1 , ;, for k 2 N+ .
(v) The L-stable classes are ⌦, Dk , D0 , ;, for k 2 N+ .
(vi) The Sc -stable classes are ⌦, Ca , Ea , Pa , Ca \ Eb , X1 \ Pa , X1 \ Ca \ Eb , D0 , D0 \ Ca , ;, for a, b 2 {0, 1}.
(vii) The S-stable classes are ⌦, X1 \ Pa , D0 , ;, for a 2 {0, 1}.
(viii) The Tc -stable classes are ⌦, Ca , Ea , P0 , Ca \ Eb , D0 , D0 \ Ca , ;, for a, b 2 {0, 1}
(ix) The T0 -stable classes are ⌦, C0 , D0 , D0 \ C0 , ;.
(x) The T1 -stable classes are ⌦, E1 , D0 , D0 \ C1 , ;.
(xi) The ⌦-stable classes are ⌦, D0 , ;.
References
[1] Erhard Aichinger and Peter Mayr. Finitely generated equational classes. J. Pure Appl. Algebra 220 (2016)
2816–2827.
[2] Erhard Aichinger and Bernardo Rossi. A clonoid based approach to some finiteness results in universal algebraic
geometry. Algebra Universalis 81(1) (2020), Paper No. 8, 7 pp.
[3] Moncef Bouaziz, Miguel Couceiro, and Maurice Pouzet. Join-irreducible Boolean functions. Order 27 (2010)
261–282.
[4] Miguel Couceiro and Stephan Foldes. Definability of Boolean function classes by linear equations over GF(2).
Discrete Appl. Math. 142 (2004) 29–34.
[5] Miguel Couceiro and Stephan Foldes. Functional equations, constraints, definability of function classes, and
functions of Boolean variables. Acta Cybernet. 18 (2007) 61–75.
[6] Miguel Couceiro and Stephan Foldes. Function classes and relational constraints stable under compositions with
clones. Discuss. Math. Gen. Algebra Appl. 29 (2009) 109–121.
[7] Miguel Couceiro and Maurice Pouzet. On a quasi-ordering on Boolean functions. Theoret. Comput. Sci. 396
(2008) 71–87.
[8] Oya Ekin, Stephan Foldes, Peter L. Hammer, and Lisa Hellerstein. Equational characterizations of Boolean
function classes. Discrete Math. 211 (2000) 27–51.
[9] Stefano Fioravanti. Closed sets of finitary functions between finite fields of coprime order. arXiv:1910.11759.
[10] Stephan Foldes and Grant R. Pogosyan. Post classes characterized by functional terms. Discrete Appl. Math. 142
(2004) 35–51.
[11] Sebastian Kreinecker. Closed function sets on groups of prime order. J. Mult.-Valued Logic Soft Comput. 33 (2019)
51–74.
[12] Erkko Lehtonen. Descending chains and antichains of the unary, linear, and monotone subfunction relations.
Order 23 (2006) 129–142.
[13] Erkko Lehtonen and Jaroslav Nešetřil. Minors of Boolean functions with respect to clique functions and hypergraph
homomorphisms. European J. Combin. 31 (2010) 1981–1995.
[14] Erkko Lehtonen and Ágnes Szendrei. Equivalence of operations with respect to discriminator clones. Discrete
Math. 309 (2009) 673–685.
[15] Erkko Lehtonen and Ágnes Szendrei. The submaximal clones on the three-element set with finitely many relative
R-classes. Discuss. Math. Gen. Algebra Appl. 30 (2010) 7–33.
[16] Erkko Lehtonen and Ágnes Szendrei. Clones with finitely many relative R-classes. Algebra Universalis 65 (2011)
109–159.
[17] Erkko Lehtonen and Ágnes Szendrei. Partial orders induced by quasilinear clones. In Contributions to General
Algebra 20, Proceedings of the Salzburg Conference 2011 (AAA81), pages 51–84. Verlag Johannes Heyn,
Klagenfurt, 2012.
[18] Nicholas Pippenger. Galois theory for minors of finite functions. Discrete Math. 254 (2002) 405–419.
[19] Emil L. Post. The Two-Valued Iterative Systems of Mathematical Logic. Annals of Mathematics Studies, no. 5.
Princeton University Press, Princeton, 1941.
[20] Svetlana N. Selezneva and Anton V. Bukhman. Polynomial-time algorithms for checking some properties of
Boolean functions given by polynomials. Theory Comput. Syst. 58 (2016) 383–391.
[21] Athena Sparks. On the number of clonoids. Algebra Universalis 80(4) (2019), Paper No. 53, 10 pp.