Miguel Couceiro
email: miguel.couceiro@loria@inria.fr

Bruno Teheux
email: bruno.teheux@uni.lu

PIVOTAL DECOMPOSITION SCHEMES INDUCING CLONES OF OPERATIONS

We study pivotal decomposition schemes and investigate classes of pivotally decomposable operations. We provide sufficient conditions on pivotal operations that guarantee that the corresponding classes of pivotally decomposable operations are clones, and show that under certain assumptions these conditions are also necessary. In the latter case, the pivotal operation together with the constant operations generate the corresponding clone.

Introduction and Motivation

Several classes of operations have the remarkable feature that each member f : A n → A is decomposable into simpler operations that are then combined by a single operation, in order to retrieve the values of the original operation f . A noteworthy example is the class of Boolean functions f : {0, 1} n → {0, 1} that can be decomposed into expressions of the form [START_REF] Barlow | Importance of system components and fault tree events[END_REF] f (x) = x k f (x 1 k ) + (1 -x k )f (x 0 k ), for x = (x 1 , . . . , x n ) ∈ {0, 1} n and k ∈ [n], and where x c k denotes the n-tuple obtained from x by substituting its k-th component by c ∈ {0, 1}. Such decomposition scheme is referred to as Shannon decomposition (or Shannon expansion) [START_REF] Shannon | A symbolic analysis of relay and switching circuits[END_REF], or pivotal decomposition [START_REF] Barlow | Importance of system components and fault tree events[END_REF]. Boolean functions are similarly decomposable into expressions in the language of Boolean lattices [START_REF] Bandelt | Median algebras[END_REF] f

(x) = (x k ∧ f (x 1 k )) ∨ (x k ∧ f (x 0 k )) where x k = 1 -x k .
More recent examples include the class of polynomial operations over a distributive lattice (essentially, combinations of variables and constants using the lattice operations ∧ and ∨) that were shown in [START_REF] Marichal | Weighted lattice polynomials[END_REF] to be decomposable into expressions of the form

(3) f (x) = med(f (x 0 k ), x k , f (x 1 k ))
, where med is the ternary lattice polynomial given by med(x 1 , x 2 , x 3 ) = (

x 1 ∧ x 2 ) ∨ (x 1 ∧ x 3 ) ∨ (x 2 ∧ x 3 ) = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 3 ) ∧ (x 2 ∨ x 3 ).
The latter decomposition scheme is referred to as median decomposition in [START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF] and [START_REF] Marichal | Weighted lattice polynomials[END_REF]. We refer the reader to [START_REF] Miyata | Realization of arbitrary logical functions using majority elements[END_REF][START_REF] Tohma | Decompositions of logical functions using majority decision elements[END_REF][START_REF] Couceiro | An algorithm for producing median normal form representations for Boolean functions[END_REF] for applications of the median decomposition formula to obtain median representations of Boolean functions.

Note that decomposition schemes (1), ( 2) and (3) share the same general form, namely, f (x) = Π(x k , f (x 1 k ), f (x 0 k )). Indeed,

• in [START_REF] Barlow | Importance of system components and fault tree events[END_REF] we have Π(x, y, z) = xy + (1 -x)z, Date: Thursday 12 th January, 2017,22:41.

1

• in [START_REF] Bandelt | Median algebras[END_REF] we have Π(x, y, z) = (x ∧ y) ∨ (x ∧ z), and • in (3) we have Π(x, y, z) = med(x, y, z).

These facts were observed in [START_REF] Marichal | Pivotal decompositions of functions[END_REF] where such pivotal decomposition schemes were investigated. These preliminary efforts were then further pursued under the observation that certain classes of pivotal operations fulfill certain closure requirements, notably, closure under functional composition. This led to the study [START_REF] Couceiro | Clones of pivotally decomposable functions[END_REF] of those classes of pivotally decomposable operations that constitute clones. In particular, we presented conditions on pivotal operations to ensure that the corresponding classes of pivotally decomposable operations constitute clones. However, several questions were stated without being answered. In this paper we settle many of these questions and provide new insights in this line of research.

The paper is organised as follows. In Section 2 we recall basic notions and terminology that will be used throughout the paper (Subsection 2.1). We also introduce the concepts of pivotal operation and that of pivotally decomposable class (Subsection 2.2) and discuss normal form representations that arise from such pivotal decompositions (Subsection 2.3). Moreover, we investigate certain symmetry properties that are common to pivotal operations (Subsection 2.4). In Section 3 we consider the problem of describing classes of pivotally decomposable operations that are clones. A general solution to this problem still eludes us, but we provide several sufficient conditions on pivotal operations that ensure the latter (Subsection 3.1). In fact, we show that under certain assumptions many of these conditions are also necessary (Subsection 3.2). The question of determining sets of generators for clones of pivotally decomposable operations is also addressed and partially answered. Taking this framework further into the realm of clone theory, many natural questions emerge. For instance, we construct an example of a pivotal operation Π for which the class of Π-decomposable operations is a clone that does not contain Π (Subsection 3.3); such an example is shown not to exist in the case of Boolean functions. Further questions that remain open are then discussed in Section 4.

Basic notions and notation

In this section we recall basic terminology used throughout the paper. In particular, we introduce the concepts of pivotal operation and of pivotally decomposable class, and we observe that, under certain conditions, pivotal decompositions lead to normal form representations that use a unique non trivial connective, namely, the pivotal operation. In the last subsection we investigate symmetric properties of pivotal operations and present some characterizations. A , S ⊆ [n] and a ∈ A n we define the S-section f a S of f as the |S|-ary operation on A defined by f a S (x) = f (a x S ), where a x S is the n-tuple whose i-th coordinate is x i , if i ∈ S, and a i , otherwise. For k ∈ [n], we say that the k-th

argument of f ∈ O (n) A is essential if there is a tuple b ∈ A n such that f b k is non-constant.
Otherwise, we way that it is inessential.

A clone on A is a set C ⊆ O A of operations on A that (1) contains all projections on A, i.e., operations p n i : A n → A given by

p n i (x 1 , . . . , x n ) = x i , for i ∈ [n], and
(2) is closed under taking functional compositions, i.e., if

f ∈ C ∩ O (n) A and g 1 , . . . , g n ∈ C ∩ O (m) A , then their composition f (g 1 , . . . , g n ) ∈ O (m) A that is defined by f (g 1 , . . . , g n )(x) = f (g 1 (x), . . . , g n (x)) (x ∈ A m ) also belongs to C.
In the case when A is finite, the set of all clones on A forms an algebraic lattice, where the lattice operations are the following: meet is the intersection, join is the smallest clone that contains the union. The greatest element is the clone O A of all operations on A; the least element is the clone J A of all projections on A. For sets A of cardinality at least 3, this lattice is uncountable, and its structure remains a topic of current research; see, e.g., [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF][START_REF] Lau | Function Algebras on Finite Sets[END_REF]. In the case when |A| = 2, the lattice of clones on A is countably infinite, and it was completely described by E. Post [START_REF] Post | The Two-Valued Iterative Systems of Mathematical Logic[END_REF]. In particular, it follows that each Boolean clone can be generated by a finite set of Boolean functions. For instance,

• the clone O {0,1} of all Boolean functions can be generated by {¬, ∧} or, equivalently, by {0, ¬, med}; • the clone M of all monotone Boolean functions, i.e., verifying x ≤ y =⇒ f (x) ≤ f (y), can be generated by {0, 1, ∧, ∨} or, equivalently, by {0, 1, med}; • the clone SM of all self-dual monotone Boolean functions, i.e., monotone operations verifying f (¬x) = ¬f (x), is generated by {med}.

For further background see, e.g., [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF][START_REF] Lau | Function Algebras on Finite Sets[END_REF].

Pivotal operations and pivotally decomposable classes.

In what follows, A denotes an arbitrary fixed nonempty set, and 0 and 1 are two fixed elements of A. In the setting of operations, the notion of pivotal operation Π and that of Π-decomposable operation can be defined as follows.

Definition 2.1 (Definition 2.1 in [START_REF] Marichal | Pivotal decompositions of functions[END_REF]). A pivotal operation on A is a ternary operation Π on A that satisfies the equation ( 4) Π(x, y, y) = y.

If Π is a pivotal operation, then f ∈ O (n) A is Π-decomposable if (5) f (x) = Π(x i , f (x 1 i ), f (x 0 i )), x ∈ A n , i ∈ [n].
Also, we denote by Λ Π the class of Π-decomposable operations on A.

Note that condition (4) ensures that Π-decomposability of an operation does not depend on its inessential arguments. Indeed, if the ith

argument of f is inessential, then f (x) = f (x 1 i ) = f (x 0 i ) for every x ∈ A n . It follows from (4) that f (x) = Π(x i , f (x 1 i ), f (x 0 i )) for any x ∈ A n .
In particular, we can state the following result. Lemma 2.2. If Π is a pivotal operation, then every constant operation on A is Π-decomposable.

Normal form representations induced by pivotal decompositions.

Note that if an operation f is Π-decomposable, then we arrive at a representation of f by an expression built from the pivotal operation Π and applied to variables and constants, by iterating its Π-decomposition expression [START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF]. This fact motivates the following notion of Π-normal form.

Definition 2.3. Let Π ∈ O (3)

A . We define the classes of k-ary Π-normal forms N k Π inductively on k ≥ 0 by the following rules.

(1)

N 0 Π = O (0)
A .

(2) For any k ≥ 0, the class N k+1 Π is defined by

N k+1 Π = {Π(x k+1 , g, g ′ ) | g, g ′ ∈ N k Π }. We denote by N Π the class ∪ k≥0 N k Π of the Π-normal forms. Observe that N k Π ⊆ O (k)
A for every k ≥ 0. By repeated applications of (5), we get the following result.

Proposition 2.4. If Π is a pivotal operation, then Λ Π ⊆ N Π .
2.4. Symmetric pivotal operations. As we will see later in the paper, a pivotal operation Π is not necessarily Π-decomposable. However, when it is, then it verifies certain symmetry properties. Consider the following equations:

Π(x, y, z) = Π(z, x, y), (6) Π(x, y, z) = Π(z, y, x), (7) Π(x, 1, 0) = x, (8)
Clearly, Π is symmetric if and only if it satisfies ( 6) and [START_REF] Couceiro | On a quasi-order on Boolean functions[END_REF]. The following result states that if Π ∈ Λ Π and satisfies ( 6) and ( 8), then it is symmetric. Proposition 2.5. If Π is a Π-decomposable pivotal operation that satisfies (8) and [START_REF] Couceiro | Clones of pivotally decomposable functions[END_REF], then it satisfies [START_REF] Couceiro | On a quasi-order on Boolean functions[END_REF]. In particular, Π is a symmetric operation.

Proof. We obtain successively

Π(x, y, z) = Π(x, Π(1, y, z), Π(0, y, z)) (9) = Π(x, Π(y, Π(1, 1, z), Π(1, 0, z)), Π(z, Π(0, y, 1), Π(0, y, 0))) (10) = Π(x, Π(y, 1, z), Π(z, y, 0)) (11)
= Π(x, Π(z, y, 1), Π(z, y, 0)) [START_REF] Lehtonen | Equivalence of operations with respect to discriminator clones[END_REF] = Π(z, y, x). [START_REF] Marichal | Weighted lattice polynomials[END_REF] where ( 9), [START_REF] Lau | Function Algebras on Finite Sets[END_REF] and [START_REF] Marichal | Weighted lattice polynomials[END_REF] were obtained by Π-decomposability of Π, and where [START_REF] Lehtonen | Descending chains and antichains of the unary, linear, and monotone subfunction relations[END_REF] and [START_REF] Lehtonen | Equivalence of operations with respect to discriminator clones[END_REF] were obtained by ( 4), ( 8) and [START_REF] Couceiro | On a quasi-order on Boolean functions[END_REF]. □

Under the assumption of Π-decomposability of Π and (8), symmetry of a pivotal operation Π can be characterized in the following way. Theorem 2.6. Le Π be a Π-decomposable pivotal operation that satisfies [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF] . The following conditions are equivalent.

(i) Π is symmetric.

(ii) Π satisfies the equations Π(0, 1, 0) = Π(0, 0, 1) and Π(1, 1, 0) = Π(1, 0, 1).

Proof. It is clear that (i) implies (ii). Let us prove that (ii) implies (i). It suffices to prove that Π satisfies

Π(x, y, z) = Π(x, z, y), ( 14
) Π(x, y, z) = Π(y, x, z). ( 15
)
First, note that for every x ∈ A we obtain successively Π(x, 1, 0) = Π(x, Π(1, 1, 0), Π(0, 1, 0)) = Π(x, Π(1, 0, 1), Π(0, 0, 1)) = Π(x, 0, 1), [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF] where the first identity is obtained by [START_REF] Couceiro | On a quasi-order on Boolean functions[END_REF], the second by contition (ii) and the last one by Π-decomposability of Π. Then, for every y ∈ A we have Π(x, y, 0) = Π(y, Π(x, 1, 0), Π(x, 0, 0)) = Π(y, Π(x, 0, 1), Π(x, 0, 0)) [START_REF] Post | The Two-Valued Iterative Systems of Mathematical Logic[END_REF] = Π(x, 0, y), [START_REF] Shannon | A symbolic analysis of relay and switching circuits[END_REF] where the first and last identities are obtained by decomposability of Π, and the second by [START_REF] Pippenger | Galois theory for minors of finite functions[END_REF]. Using a similar argument, we obtain [START_REF] Tohma | Decompositions of logical functions using majority decision elements[END_REF] Π(x, y, 1) = Π(x, 1, y).

Finally, we obtain for any z ∈ A Π(x, y, z) = Π(z, Π(x, y, 1), Π(x, y, 0)) = Π(z, Π(x, 1, y), Π(x, 0, y))

(20) = Π(x, z, y),
where the first and last identities are obtained by decomposability (5) of Π, and the second by ( 18) and ( 19). This proves that ( 14) holds. Now, using ( 8) and ( 4) in the first identity in [START_REF] Post | The Two-Valued Iterative Systems of Mathematical Logic[END_REF] we obtain that (21) Π(x, y, 0) = Π(y, x, 0).

Similarly, we have Π(x, y, 1) = Π(y, Π(x, 1, 1), Π(x, 0, 1)) = Π(y, 1, x),

= Π(y, x, 1), ( 22
)
where the first identity is obtained by decomposability of Π, the second by ( 4), ( 16) and [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF], and the last one by [START_REF] Tohma | Decompositions of logical functions using majority decision elements[END_REF]. Using ( 21) and ( 22) in the first identity of (20), we obtain (15) by Π-decomposability of Π. □

Clones of pivotally decomposable operations

In Subsection 3.1, we provide sufficient conditions on a pivotal operation Π for Λ Π to be a clone, and in Subsection 3.2, we prove that these conditions are also necessary under the assumption that Π belongs to Λ Π , and satisfies two additional equations (30) and (31) that involves only Π, and the elements 0 and 1. Certain natural questions are also discussed and answered negatively by counter-examples that are constructed in Subsection 3.3.

3.1.

Sufficient conditions for Λ Π to be a clone. Let us consider the following equations:

Π(Π(x, y, z), t, u) = Π(x, Π(y, t, u), Π(z, t, u)). ( 23
)
The relevance of property ( 23) is made apparent by the following lemma. Lemma 3.1. Let Π be a pivotal operation that satisfies (23). If f : A n → A and g 1 , . . . , g n : A m → A are Π-decomposable, then so is f (g 1 , . . . , g n ).

Proof. For every i ∈ [n] let g ′

i : A nm → A be the operation defined by g ′ i (x) = g i (x i ) where x i = (x (i-1)m+1 , . . . , x im ). We prove that f

(g ′ 1 , . . . , g ′ n ) is Π-decomposable. For x ∈ A nm , set c 0 x = f (0, g ′ 2 (x), . . . , g ′ n (x)), c 1 x = f (1, g ′ 2 (x), . . . , g ′ n (x)), a 0 x = g ′ 1 (0, x 2 , . . . , x nm ), a 1 x = g ′ 1 (1, x 2 , . . . , x nm ). We obtain by Π-decomposability of f that f (g ′ 1 (x), . . . , g ′ n (x)) = Π(g ′ 1 (x), c 1
x , c 0 x ). By iterating the pivotal decomposition expression (to each argument), we get the following equalities

Π(g ′ 1 (x), c 1 x , c 0 x ) = Π(Π(x 1 , a 1 x , a 0 x ), c 1 x , c 0 x ), = Π(x 1 , Π(a 1 x , c 1 x , c 0 x ), Π(a 0 x , c 1 x , c 0 x )), = Π(x 1 , f (g ′ 1 , . . . , g ′ n )(x 1 1 ), f (g ′ 1 , . . . , g ′ n )(x 0 1 )),
where the first equality is obtained by Π-decomposability of g ′ 1 , the second one by equation ( 23) and the last one by Π-decomposability of f . Thus, we have proved that condition (5) holds for f (g ′ 1 , . . . , g ′ n ) and i = 1. We can proceed in a similar way to obtain

(24) f (g ′ 1 (x), . . . , g ′ n (x)) = Π(x ℓ , f (g ′ 1 , . . . , g ′ n )(x 1 ℓ ), f (g ′ 1 , . . . , g ′ n )(x 0 ℓ )), for every ℓ ∈ [nm]
. The decomposability of Π(g 1 , . . . , g n ) follows from ( 24) by identifying all arguments in {x i , x m+i , . . . , x (n-1)m+i } for every i ∈ [m]. □

Similarly, if the pivotal operation satisfies equation ( 8), then Λ Π must contain all projections. Lemma 3.2. Let Π be a pivotal operation. The following conditions are equivalent.

(i) Π satisfies equation [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF].

(ii) Λ Π contains all projections on A.

(iii) Λ Π contains the unary projection

p 1 1 . Proof. (i) =⇒ (ii): Let n ≥ 1 and k ∈ [n]. For every i ∈ [n] such that i ̸ = k and for every x ∈ A n , Π(x i , p n k (x 1 i ), p n k (x 0 i )) = Π(x i , x k , x k ) =
x k where the last equality is obtained by [START_REF] Couceiro | An algorithm for producing median normal form representations for Boolean functions[END_REF].

If i = k, then Π(x i , p n k (x 1 i ), p n k (x 0 i )) = Π(x k , 1, 0) = x k
where the last equality is obtained by [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. We conclude that p n k ∈ Λ Π . (ii) =⇒ (iii): Trivial. (iii) =⇒ (i): If Λ Π contains the unary projection p 1 1 , then for every x ∈ A we have x = p 1 1 (x) = Π(x, 1, 0). Thus Π satisfies equation [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF], and the proof of the lemma is now complete. □ By combining Lemmas 2.2, 3.1, and 3.2, we obtain the following result.

Proposition 3.3. Suppose that Π is a pivotal operation that satisfies equation (23).

Then Λ Π is a clone if and only if Π satisfies equation [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. In the latter case, Λ Π is a clone that contains all constant operations.

We illustrate the previous results by analyzing the particular case of Boolean functions.

Example 3.4. Let Π be a Boolean pivotal operation such that Λ Π is a clone. According to Proposition 3.2, the operation Π satisfies equation [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. Hence, the unary sections Π(x, 0, 0) and Π(x, 1, 1) are determined by (4) while the value of the section Π(x, 1, 0) is determined by ( 8):

(25) Π(x, 0, 0) = 0, Π(x, 1, 1) = 1, Π(x, 1, 0) = x.
Moreover, it is not difficult to check that the four possibilities for the unary section Π(x, 0, 1), namely,

Π 0 (x, 0, 1) = x, Π 1 (x, 0, 1) = x, Π 2 (x, 0, 1) = 0, Π 3 (x, 0, 1) = 1,
give rise to operations Π 0 , . . . , Π 3 that satisfy equation (23). Simple computations then show that we must have

Π 0 (x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z), Π 1 (x, y, z) = (x ∧ y) ∨ (x ∧ z), Π 2 (x, y, z) = y ∧ (x ∨ z), Π 3 (x, y, z) = z ∨ (x ∧ y).
Hence, the clones Λ Π0 , . . . , Λ Π3 are as follows:

(a) Λ Π0 is the clone M of all monotone Boolean functions, since Π 0 = med; (b) Λ Π1 is the clone O {0,1} of all Boolean functions, since Π 1 is the pivotal operation used in Shannon decomposition; (c) Λ Π2 is the clone M of all monotone Boolean functions, since Π 2 (x, y, 0) = y ∧ x and Π 2 (x, 1, z) = x ∨ z, and every composition of Π 2 with projections or constants is monotone; (d) Λ Π3 is the clone M of all monotone Boolean functions (by a similar argument to that used for Λ Π2 ). The situation can be summarized by the following result. 3.2. The case of a pivotally decomposable Π. In the section, we derive results about clones of Π-decomposable operations under the additional assumption that the operation Π itself is Π-decomposable, i.e., that Π ∈ Λ Π .

The next result states that under this assumption, the pivotal operation together with constant maps suffice to construct expressions representing each member of Λ Π . Proposition 3.6. Let Π be a pivotal operation such that Λ Π is a clone that contains Π. Then Λ Π is the clone generated by Π and the constant maps. In particular,

Λ Π = N Π .
Proof. Let C be the clone generated by Π and the constant operations. We have to prove that Λ Π = C. The right to left inclusion is trivial since Λ Π is a clone and contains each of the mentioned generators of C by assumption and Lemma 2.2. We derive the converse inclusion and the last part of the statement from the following sequence of inclusions,

Λ Π ⊆ N Π ⊆ C ⊆ Λ Π ,
where the first inclusion is obtained by Proposition 2.4, the second inclusion follows from the definitions of N Π and C, and the third inclusion is a consequence of the first part of this proof. □

In the presence of a Π-decomposable operation Π, equation ( 8) has interesting consequences on the equational theory of the the algebra ⟨A, Π, 0, 1⟩, where Π is a pivotal operation. Lemma 3.7. If Π is a pivotal operation on A that satisfies [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF], then it satisfies the following equations:

Π(0, 1, z) = z, (26) Π(1, 1, z) = 1, (27) Π(0, y, 0) = 0, (28) Π(1, y, 0) = y. ( 29
)
Proof. The proof follows from straightforward applications of equations ( 5) and [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. For instance, we obtain successively

Π(0, 1, z) = Π(z, Π(0, 1, 1), Π(0, 1, 0)) = Π(z, 1, 0) = z,
where the first equality is obtained by [START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF] and the two last ones by [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. □

According to Proposition 3.3, if Π is a pivotal operation that satisfies equations ( 8) and (23), then Λ Π is a clone. In the next theorem, we prove that the converse Theorem 3.8 gives a characterization of pivotal operations Π such that Λ Π is a clone, under the assumption that Π ∈ Λ Π . We now give an example of a pivotal operation Π such that Λ Π is a clone that does not contain Π. Note however that Example 3.4 shows that such a Π does not exist in the case of Boolean functions. First, observe that Π ̸ ∈ Λ Π . Indeed, for any x ∈ A we have on the one hand Π(x, a, a) = a while Π(a, Π(a, Π(x, 1, a), Π(x, 0, a)) = Π(a, 1, 1) = 1. According to Proposition 3.3, it suffices to prove that Π satisfies equation ( 23). If t = u or (t, u) ∈ {(a, 0), (a, 1), (1, a), (0, a)} then Π(x, t, u) is constant and (23) holds trivially. If (t, u) = (1, 0) then Π(x, t, u) is the first projection and (23) holds as well. It remains to consider the case (t, u) = (0, 1). We have to prove

Conclusions and Further Research

In this paper, we studied pivotal decompositions of operations from a clone theory perspective, and presented a characterization of classes of Π-decomposable operations that are clones in the case when the pivotal operation Π is itself Πdecomposable and satisfies (30) and (31). However in Example 3.13 we showed that there exists a clone of Π-decomposable operations that does not contain Π, i.e., Π is not Π-decomposable. This leaves open a complete description of classes of pivotally decomposable operations that are clones. Moreover, once such a description is obtained, a structural analysis of the set of all pivotally decomposable clones is to be expected.

Another topic that will deserve our attention is motivated by Theorem 2.6 that states that if a pivotal operation Π is a Π-decomposable and satisfies Π(x, 1, 0) = x, Π(0, 0, 1) = 0, and Π(1, 0, 1) = 1, then Π is symmetric and hence is a majority operation. Furthermore, if Π satisfies (23), then Π is a median operation (see [START_REF] Bandelt | Median algebras[END_REF] and the bibliography therein). These observations establish noteworthy connections between pivotally decomposable classes and median algebras, and should deserve a deeper study in future research.

As a third line of research that emerges from this paper deals with normal form representations of operations arising from pivotal decomposition schemes. Proposition 2.4 provides normal form representations for the elements of a pivotally decomposable class. Here, determining canonical expressions for these representations based on the pivotal operation, as well as studying the complexity of such representations (e.g., with respect to classical normal form representations) constitute an interesting topic of research which is under current investigation. We envision a similar study to that of [START_REF] Couceiro | Composition of Post classes and normal forms of Boolean functions[END_REF] where, in particular, it was shown that normal form representations of Boolean functions that use the ternary median as the only logical connective, produce asymptotically shorter representations than the classical DNF, CNF and polynomial representations.

2. 1 .

 1 Preliminaries: Clones of operations. For any positive integer n, we denote by [n] the set {1, . . . , n}. For a nonempty set A, a function f : A n → A is called an n-ary operation on A. We denote by O (n) A the set of n-ary operations on A and by O A = ∪ n≥1 O (n) A the set of operations on A. For any f ∈ O (n)

Proposition 3 . 5 .

 35 If C is Boolean clone, then there is a Boolean pivotal operation Π such that C = Λ Π if and only if C is the clone of all monotone Boolean functions or the clone of all Boolean functions.

Example 3 . 13 .

 313 Let A = {0, a, 1} and N : A → A be the map defined by N (0) = 1, N (a) = a, and N (1) = 0. Define Π : A 3 → A as the map that satisfies (8), (4) and Π(x, 0, 1) = N (x)

  , N (y), N (z)) = N (Π(x, y, z)).If y = z then or (y, z) ∈ {(a, 0), (a, 1), (1, a), (0, a)} then(43) clearly holds by (39) -(42). If (y, z) ∈ {(0, 1), (1, 0)} then (43) holds by (38).

Acknowledgment

This work was supported by the internal research project F1R-MTH-PUL-15MRO3 of the University of Luxembourg.

statement also holds, under the assumption that Π ∈ Λ Π and that Π(Π(1, 0, 1), 0, 1) = Π(1, Π(0, 0, 1), Π(1, 0, 1)), (30) Π(Π(0, 0, 1), 0, 1) = Π(0, Π(0, 0, 1), Π(1, 0, 1)). (31) Theorem 3.8. Let Π be a Π-decomposable pivotal operation that satisfies (30) and (31). The following conditions are equivalent:

(i) Λ Π is a clone, (ii) Π satisfies equations [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF] and (23).

In this case, Λ Π is the clone generated by Π and the constant maps.

Proof. Proposition 3.3 states that (ii) =⇒ (i). Conversely, assume that Π is a pivotal operation such that Λ Π is a clone that contains Π. By Lemma 3.2, it follows that Π satisfies equation [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF].

We prove that (23) also holds. In what follows, we use without further warning the fact that Λ Π is a clone that contains Π and every constant operation to apply [START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF] to operations which are compositions of Π and constant ones.

Hence, if L(x, y, z) and R(x, y, z) denote the operations given by the left-hand side and right-hand side of equation ( 23), respectively, we have

)) .

To prove that L(x, y, z) = R(x, y, z) it suffices to prove that the two following equations hold:

We prove that (32) holds (with the help of (30)). Equation (33) can be obtained in a similar way (with the help of (31)).

By decomposing with respect to y, we obtain that the right-hand side of (32

while the left-hand side of (32) is equal to

Hence, to prove that equation (32) holds, we first observe that

, by ( 5), (4),

) by [START_REF] Couceiro | Polynomial functions over bounded distributive lattices[END_REF].

It remains to prove that

By decomposing with regard to z we obtain

and it suffices to prove that

Observe that by decomposing with respect to u,

where we have applied (28) to obtain the second identity. Hence, to prove (35) it suffices to prove that

By ( 5) we obtain

which proves (37). Next, we observe that

Π(0, 0, 1), Π(1, 0, 1)

)) .

We conclude that (36) is satisfied by applying (31), which holds by assumption. □ Since (30) and ( 31) are instances of (23), Theorem 3.8 can be restated as follows.

Corollary 3.9. Let Π be a Π-decomposable pivotal operation. The following conditions are equivalent:

(i) Λ Π is a clone and Π satisfies (30) and (31), (ii) Π satisfies (8) and (23).

By noting that equations (30) and (31) are satisfied by a symmetric pivotal operation that satisfies [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF], we obtain the following corollary. Corollary 3.10. Let Π be a symmetric Π-decomposable pivotal operation that satisfies [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. The following conditions are equivalent: (i) Λ Π is a clone, (ii) Π satisfies (23).

Further issues and counter-examples.

In view of Theorem 3.8 and Corollary 3.9, a natural question arises: can the Π-decomposability of Π be deduced from equations ( 8) and (23)? Example 3.4 shows that the answer is positive if Π is a Boolean pivotal operation. Now, we prove that it is not true in general. We set

Proposition 3.11. Let Π be a pivotal operation that satisfies [START_REF] Denecke | Universal Algebra and Applications in Theoretical Computer Science[END_REF]. If there exits a function f : A ∆ → A such that Π(x, y, z) = f (y, z) for every (y, z) ∈ A ∆ , then Π also satisfies (23).

Proof. Note first that Π is well defined by the conditions in the statement. Moreover, equations ( 4) and (8) ensure that (23) is satisfied when t = u or (t, u) = (1, 0), respectively. Now, if (t, u) ∈ A ∆ , then Π(Π(x, y, z), t, u) = f (t, u) = Π(x, f (t, u), f (t, u)) = Π(x, Π(y, t, u), Π(z, t, u)).

This shows that (23) does indeed hold for such a Π. □ Example 3.12. Assume that A has at least three elements 0, 1, 2. Let f : A ∆ → A be any mapping that satisfies f (2, 0) = f (2, 1) ̸ = f (2, 2). Then the pivotal operation Π defined as in Proposition 3.11 is not Π-decomposable since Π(1, 2, 2) = f (2, 2) while Π(2, Π(1, 2, 1), Π(1, 2, 0)) = f (2, 0).