Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 1, 181-204.

Clones Closed with Respect to Permutation Groups or Transformation Semigroups

V.V. Gorlov R. Pöschel

Dept. of Mathematics, Byelorussian State University pr-t F. Skoriny 4, 220050 Minsk, Belarus e-mail: valera@gorlov.belpak.minsk.by

Technische Universität Dresden, Institut für Algebra 01062 Dresden, Germany e-Mail: poeschel@math.tu-dresden.de

Abstract. This paper presents a new approach to the classification of finite algebras with respect to actions of permutation groups or transformation semigroups on the clone of term operations. In particular it is a contribution to the structural investigation of the (uncountable) lattice L_{A} of clones on a finite set A, which can be divided into (sometimes finitely many) intervals represented by so-called Gclones. A Galois theory for G-clones is developed. Concrete results are presented for clones — and, more generally, for closed classes — on base sets A with two or three elements.

Introduction

This paper contributes to the classification of finite algebras with the same underlying set A. A finite algebra A = ⟨A; F ⟩ consists of a finite set A together with a (possibly infinite) set of (fundamental) operations (e.g. finite groups, rings, lattices, …). For fixed A with |A| ≥ 3, the set of all algebras on A is uncountable. The set T (A) of all term operations is a natural closure of F consisting of the projections and all compositions of the fundamental operations, i.e. T (A) is the so-called clone of operations ⟨F ⟩_{O_{A}} generated by F. Thus we can compare algebras A = ⟨A; F ⟩ and A′ = ⟨A; F′⟩ via their clone of operations:

A ≤ A′ ⟺ T (A) = ⟨F ⟩_{O_{A}} ⊆ ⟨F′⟩_{O_{A}} = T (A′).

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1998 Heldermann Verlag

With respect to this preorder two algebras are “the same” if they are term equivalent ([23, 4.139]), i.e. if they have the same underlying set and the same term operations. Every algebra A = ⟨A; F ⟩ is term equivalent to the algebra A = ⟨A; T (A)⟩ and the algebras of the form ⟨A; ⟨F ⟩_{O_{A}}⟩ form a transversal for term equivalence.

Thus, up to term equivalence, the classification of finite algebras with underlying set A leads to the classification of clones, i.e. to the investigation of the lattice^{1} L_{A} of all clones on A.

More generally, the same approach can be done with closed classes instead of clones. The closed class generated by F ⊆ O_{A} is the set of all compositions of functions from F (without using the projections as in the clone case).

The lattice L_{A} is completely known (by a result of E.L. Post obtained in 1921, cf. [27]) for Boolean functions (|A| = 2), it is countable; however L_{A} is uncountable for |A| ≥ 3 ([16]). There is not much hope to get an effective description of the clone lattice on an at least threeelement set. Many efforts were made to understand the structure of L_{A}, e.g. it is atomic and dually atomic, all maximal clones (= dual atoms = lower neighbours of the largest clone O_{A}) are described (there are finitely many [17], [28]) while a complete description of all minimal clones (= atoms) still is an open problem.

There are two general strategies: one can restrict to special sublattices (e.g. intervals) of L_{A} or one introduces equivalence relations between clones in order to partition the lattice L_{A} into smaller pieces. From the universal algebraic point of view isomorphic algebras are the same. However there is a strong restriction: the algebras under consideration must be of the same type. In order to compare algebras of various types one has to use the more general notion of weak isomorphism ([22], [8], [11]) which, in fact, induces an isomorphism of the corresponding clones, too (for an approach via crypto-isomorphisms with respect to a general closure operator we refer to [26]). Two algebras A = ⟨A; F ⟩ and A′ = ⟨A; F′⟩ are weakly isomorphic if A is term equivalent to A^{σ} = ⟨A; F^{σ}⟩ for some permutation σ : A ↦ A (cf. 1.2 below). But also these weak isomorphisms cannot reduce considerably the amount of algebras or corresponding clones (there remain uncountably many). Consequently, one should look for stronger equivalences between clones.

In this paper we shall develop the following approach. If a function f : A^{n} → A is given (in a clone F) we shall assume that every function f^{s} with the same behaviour as f but “up to renaming (via s) the elements of A” is also given (where s ∈ G is a permutation on A in a subgroup G ≤ S_{A}). This action of S_{A} on clones gives a closure operator F ↦ ^{G}F on L_{A} (cf. 2.2). Then two clones (or algebras) will be “(∨_{G}-)equivalent” if their G-closures (called G-clones) coincide; the G-clone ^{G}F generated by F is the largest element in each equivalence class. The special case of self-dual clones (and closed classes) or homogeneous algebras (where f^{s} = f for each element f of the clone) is considered e.g. in [4], [5], [6], [20] and [3]. Further references can be found also in [21].

Every clone determines a least interval (in L_{A}) between G-clones to which it belongs.

1L_{A} is an algebraic lattice with respect to inclusion. The lattice operations are given in 1.1.

It turns out (by results of V. Gorlov and Nguen van Hoa [14]) that in several cases, e.g. for G = S_{A}, the lattice of G-clones even becomes finite. Thus the general problem to describe the structure of L_{A} now divides into two parts:

• describe the lattice of G-clones (or closed classes) and

• describe the equivalence classes (w.r.t. ∼_{∨_{G}} or ∼_{∧_{G}}, see 2.4 for definition). In the present paper we are mainly concerned with the first problem. We shall develop this with respect to permutation groups G (sections 1–4). We also develop a Galois theory for G-clones and corresponding relational G-clones (section 4). Instead of permutations one can also use arbitrary unary mappings h : A ↦ A. This leads to H-clones with respect to transformation semigroups H on A (sections 5–6). There are large differences between the group and the semigroup actions on clones, but both might be helpful for the structural analysis of the lattice L_{A}. For two- or three-element sets A we present (for special G and H) a list of all G- and H-clones as well as of closed classes (sections 3 and 6).

1. Preliminaries: Notions and Notations

1.1. Let O_{A}^{(n)} be the set of all n-ary operations f : A^{n} ⟶ A (of arity ar f := n) on a set A (n ∈ N^{+} = {1, 2, …, } and O_{A} := ⋃_{n=1}^{∞} O_{A}^{(n)}. The projections e_{i}^{n} ∈ O_{A}^{(n)} and constants

c_{a}^{n} ∈ O_{A}^{(n)} are defined by e_{i}^{n}(x_{1}, …, x_{n}) = x_{i} and c_{a}^{n}(x_{1}, …, x_{n}) = a (for a ∈ A). Let J_{A} denote the set of all projections. For simplicity, in case of finite A, often we shall use k := \{0, 1, …, k − 1\} or \underline{k} := \{1, 2, …, k\} instead of A. The (full) iterative (preiterative, resp.) algebra on A is the algebra

P_{A} = ⟨O_{A}; τ, ζ, Δ, ∇, ∗⟩ (P_{A}^{∗} = ⟨O_{A}; τ, ζ, Δ, ∗⟩, resp.)

of type (1,1,1,1,2) ((1,1,1,2), resp.), where the operations are defined as follows: Let f ∈ O_{A}^{(n)}, g ∈ O_{A}^{(m)}, then

(τf)(x_{1}, …, x_{n}) := f(x_{2}, x_{1}, x_{3}, …, x_{n}),
(ζf)(x_{1}, …, x_{n}) := f(x_{2}, x_{3}, …, x_{n}, x_{1}),
(Δf)(x_{1}, …, x_{n−1}) := f(x_{1}, x_{1}, …, x_{n−1}),
(∇f)(x_{1}, …, x_{n+1}) := f(x_{2}, x_{3}, …, x_{n+1}),
(f ∗ g)(x_{1}, …, x_{m}, x_{m+1}, …, x_{m+n−1}) := f(g(x_{1}, ...x_{m}), x_{m+1}, ...q, x_{m+n−1}).

For n = 1 we define τf = ζf = Δf = f. Let F ⊆ O_{A}. Then ⟨F ⟩_{P_{A}} denotes the subalgebra of P_{A} generated by F. F is called a closed class if F = ⟨F ⟩_{P_{A}}. If, in addition, F contains all projections e_{i}^{n} then F is a clone. Clones can be characterized as subalgebras of the full function algebra

\underline{O_{A}} := ⟨O_{A}; e, τ, ζ, Δ, ∇, ∗⟩

(where e = e_{1}^{1} is the identity operation). The subalgebra of \underline{O_{A}} generated by F is denoted by ⟨F ⟩_{O_{A}}, for short ⟨F ⟩.

Let L_{A} denote the lattice (w.r.t. inclusion) of all clones on A. The lattice operations meet ∧ and join ∨ are given by F_{1} ∧ F_{2} = F_{1} ∩ F_{2} and F_{1} ∨ F_{2} = ⟨F_{1} ∪ F_{2}⟩_{O_{A}}.

1.2. Let S_{A} be the full symmetric group on A. For a permutation s ∈ S_{A} and x ∈ A let x^{s} denote the image of x under s. For s ∈ S_{A} and f ∈ O_{A}^{(n)} define f^{s} by

f^{s}(x_{1}, …, x_{n}) := (f(x_{1}^{s^{−1}}, …, x_{n}^{s^{−1}}))^{s}.

The mapping ( )^{s} : O_{A} ⟶ O_{A} : f ↦ f^{s} is an inner [19] automorphism of the iterative algebra P_{A}. Note that

F^{s} := {f^{s} | f ∈ F }

is a closed class or clone, resp., whenever F is. If F^{s} = F for the clone F = T (A) := ⟨{f_{i} | i ∈ I}⟩_{O_{A}} of an algebra A = ⟨A; (f_{i})_{i∈I}⟩, then s is called weak automorphism of A ([10]). A function with f^{s} = f (or equivalently, if s is an automorphism of ⟨A; f⟩) is called s-selfdual.

1.3. A theorem of A. I. Mal’cev (cf. e.g. [19, 6.2:I]) states (here slightly reformulated):

1. All automorphisms of P_{A} are inner; consequently Aut P_{A} ≅ S_{A}. (The same holds for \underline{O_{A}}.)

2. All endomorphisms h : P_{A} ⟶ P_{A} which are not automorphisms are of the form

s_{a} : f ↦ c_{a}^{(n)} or s̃_{a} : f ↦ c_{a}^{(1)}

for f ∈ O_{A}^{(n)}, n ∈ N and fixed a ∈ A. Thus the endomorphism monoid End P_{A} is the group S_{A} together with constants s_{a} and s̃_{a} (a ∈ A).

1.4. Remarks. In case |A| = k = 2 we have Aut F ≤ S_{2} for all closed classes F ≤ P_{2}, however for k ≥ 3 there exist closed classes with non-inner automorphisms ([12]). Obviously, every automorphism of P_{A} induces an automorphism of the lattice L_{A}. Conversely, there are no other automorphisms of L_{A} (by a result of the first author (unpublished)), i.e.

Aut P_{A} ≅ Aut L_{A} ≅ S_{A} for |A| ≥ 2.

2. G-closed classes and G-clones

The following definition covers several special cases considered e.g. in [4], [20], [5], [6].

2.1. Definition. Let G be a subgroup of S_{A}. For F ⊆ O_{A} we define F^{G} := {f^{s} | f ∈ F, s ∈ G}. A clone F ≤ O_{A} or a closed class F ≤ P_{A}, resp., is called G-clone (or G-closed, resp.), if f^{s} ∈ F for all s ∈ G and f ∈ F (cf. [14]). Let L_{A,G} (L′_{A,G}, resp.) denote the set of all G-clones (G-closed classes, resp.). A function which is s-selfdual (cf. 1.2) for all s ∈ G is called G-homogeneous. A clone or a closed class F is G-homogeneous if every f ∈ F is G-homogeneous (i.e. G ⊆ Aut⟨A; F ⟩). Obviously, every G-homogeneous clone is an G-clone.

Note that F is G-closed iff F^{G} = F iff F^{s} = F for all s ∈ G. Moreover, {e}-clones are just the ordinary clones. For simplicity, in the following we mainly consider clones. However, the results can be used for arbitrary closed classes, too.

2.2. Theorem. Let G ≤ S_{A}, and F ≤ O_{A}.

(a) ^{G}F := ⟨F^{G}⟩ = ⟨ ⋃_{s∈G} F^{s}⟩_{O_{A}} is the least G-clone containing F.

(b) _{G}F := ⋂_{s∈G} F^{s} is the greatest G-clone contained in F.

(c) The set L_{A,G} of all G-clones is a sublattice of the lattice L_{A} with least element J_{A} and greatest element O_{A}: For G-clones F_{1}, F_{2} the clones ⟨F_{1} ∪ F_{2}⟩_{O_{A}} and F_{1} ∩ F_{2} are again G-clones.

Proof. (a) Obviously, every G-clone containing F must contain F^{s} for every s ∈ G, too. It remains to prove that the clone ⟨F^{G}⟩ is G-closed. Let s ∈ G, f ∈ F^{(n)}, g ∈ F^{(m)}. Then e^{s} = e, (σf)^{s} = σ(f^{s}) for every operator σ ∈ {τ, ζ, Δ, ∇} and (f ∗ g)^{s} = f^{s} ∗ g^{s} (what immediately follows from the definition). Consequently ⟨F^{G}⟩^{s} ⊆ ⟨F^{G}⟩ for s ∈ G and therefore ⟨F^{G}⟩^{G} = ⟨F^{G}⟩.

(b) ⋂_{s∈G} F^{s} is a clone (as intersection of clones) which is contained in F (put s = e), and it is

G-closed because of

( ⋂_{s′∈G} F^{s′})^{s′′} = ⋂_{s′∈G} F^{s′s′′} = ⋂_{s∈G} F^{s}.

Moreover, if F′ is a G-clone contained in F then F^{′s} = F′ is contained in every F^{s}, i.e. F′ ⊆ _{G}F.

(c) directly follows from (a) and (b) because F = F^{G} = ^{G}F = _{G}F for any G-closed F. □

2.3. Remark. The clones ^{G}F and _{G}F in 2.2 coincide with the join ⋁_{s∈G} F^{s} and meet ⋀_{s∈G} F^{s}

of the clones F^{s}(s ∈ G) in the lattice L_{A}. For G ≤ G′ ≤ S_{A} and a clone F ≤ O_{A} we always have

⋀_{s∈G′} F^{s} ⊆ ⋀_{s∈G} F^{s} ⊆ F ⊆ ⋁_{s∈G} F^{s} ⊆ ⋁_{s∈G′} F^{s}.

This motivates the following definitions.

2.4. Definitions. Let G ≤ S_{A}. For a clone F ≤ O_{A} let

G-Int(F) := [_{G}F,^{G}F]_{L_{A}} = [ ⋀_{s∈G} F^{s}, ⋁_{s∈G} F^{s}]_{L_{A}}

be its corresponding G-interval in the lattice L_{A}. Two clones F_{1}, F_{2} ≤ O_{A} are called ∧_{G}- equivalent (F_{1} ∼_{∧_{G}} F_{2}) or ∨_{G}-equivalent (F_{1} ∼_{∨_{G}} F_{2}), resp., if

⋀_{s∈G} F_{1}^{s} = ⋀_{s∈G} F_{2}^{s} or ⋁_{s∈G} F_{1}^{s} = ⋁_{s∈G} F_{2}^{s}, respectively.

2.5. Remarks. a) Obviously F is a G-clone iff G-Int(F) = {F } (i.e. F = _{G}F = ^{G}F). Both, ∼_{∧_{G}} and ∼_{∨_{G}}, are equivalence relations on L_{A}. Two clones F_{1}, F_{2} are both, ∧_{G}- and ∨_{G}- equivalent, iff the corresponding intervals coincide: G-Int(F_{1}) = G-Int(F_{2}). The set of G-clones is a transversal for the set of all ∧_{G}-equivalence classes as well as for all ∨_{G}-equivalence classes.

b) ∼_{∧_{G}} is a congruence in the semilattice ⟨L_{A}; ∧⟩ and ∼_{∨_{G}} is a congruence in ⟨L_{A}; ∨⟩, i.e. F_{1} ∼_{∧_{G}} F_{2}, F′_{1} ∼_{∧_{G}} F′_{2} implies F_{1} ∧ F′_{1} ∼_{∧_{G}} F_{2} ∧ F′_{2} (analogously for ∼_{∨_{G}}).

c) Obviously F_{1} ⊆ F_{2} implies _{G}F_{1} ⊆ _{G}F_{2} and ^{G}F_{1} ⊆ ^{G}F_{2}.

d) For clones F_{1}, F_{2} ≤ O_{A} we have _{G}F_{1} ∧ _{G}F_{2} = _{G}(F_{1} ∧ F_{2}) and ^{G}F_{1} ∨ ^{G}F_{2} = ^{G}(F_{1} ∨ F_{2}).

e) The set of intervals [F_{1}, F_{2}]_{L_{A}} with G-closed clones F_{1}, F_{2} forms a lattice w.r.t. inclusion. Meet and join in this lattice are given by

[F_{1}, F_{2}] ∧ [F′_{1}, F′_{2}] = [F_{1} ∨ F′_{1}, F_{2} ∧ F′_{2}]
[F_{1}, F_{2}] ∨ [F′_{1}, F′_{2}] = [F_{1} ∧ F′_{1}, F_{2} ∨ F′_{2}].

All G-intervals belong to this lattice, however in general it is an open problem under which conditions meet or join of G-intervals are again G-intervals.

f) The G-closure is a tool for the investigation of the lattice L_{A}. As mentioned in the introduction there is no hope to find a satisfactory full description of the uncountable lattice L_{A} (|A| ≥ 3) as in the countable case of Post’s lattice L_{2} of clones of Boolean functions. The G-closure may naturally reduce this lattice even to a finite sublattice of L_{A}. Note that under this reduction process for every G-interval [F_{1}, F_{2}] the (possibly infinite) set {F | G-Int(F) = [F_{1}, F_{2}]} reduces to two clones (namely the least and greatest elements F_{1} and F_{2} in this interval). For |A| = 2 and |A| = 3 concrete results are given in the next sections. An external characterization of the G-intervals is given in 4.5.

2.6. From the group theoretical point of view subgroups of S_{A} are considered usually up to conjugation, i.e. the groups G ≤ S_{A} and G′ := s^{−1}Gs are “the same”. Note that then the corresponding lattices L_{A,G} and L_{A,G′} are isomorphic (F ↦ F^{s} is an isomorphism). In fact, if F is G-closed then we have (F^{s})^{s^{−1}Gs} = F^{Gs} = F^{s}, i.e. F^{s} is G′-closed. Moreover, (G-Int(F))^{s} = G′-Int(F^{s}), i.e. the intervals G-Int(F) and G′-Int(F^{s}) are isomorphic for arbitrary F ≤ O_{A}. In case k = 2 conjugate groups (≤ S_{2}) coincide. For k ≥ 3 the Gintervals of F for conjugate groups G may differ.

Obviously, for H ≤ G ≤ S_{A}, every G-clone is also an H-clone (the converse does not hold in general), i.e. L_{A,G} ⊆ L_{A,H}.

We mention here the conjecture that L_{A,G} ≠ L_{A,H} for different groups G ≠ H. If this is true, the subgroup lattice of S_{A} would be dual to the lattice (w.r.t. inclusion) of all lattices L_{A,G} (G ≤ S_{A}).

2.7. From the universal algebraic point of view G-clones come into play as follows: The clone of operations F := ⟨{f_{i} | i ∈ I}⟩ of an algebra A = ⟨A; (f_{i})_{i∈I}⟩ is a G-clone (G ≤ S_{A}) iff G ⊆ wAut A, where wAut A denotes the group of weak automorphisms of A (c.f. 1.2 and [10]). Analogously, F is an homogeneous G-clone iff G ⊆ Aut A. S_{A}-clones are of special interest. If, moreover, every s ∈ S_{A} fixes the fundamental operations f_{i} of A, then f^{s} = f for every f ∈ F and A is a homogeneous algebra (for investigation of homogeneous algebras we refer to [3]).

3. G-clones on A = {0, 1} and A = {0, 1, 2}

The lattice L_{2} of all clones on A = {0, 1} is well-known. Here we use the notations for the clones given in [15]^{2}. Since S_{2} contains a single non-trivial function (negation ¬ : x ↦ ¬x), S_{2}-clones F are those which are self-dual as sets (i.e. F^{s} = F for negation s = ¬). The following result also can be derived from Theorem 1 and Proposition 1 in [10, p. 101,102].

3.1. Theorem. There are exactly 14 S_{2}-clones on A = {0, 1} :

O_{1}, O_{4}, O_{8}, O_{9}, L_{1}, L_{4}, L_{5}, D_{2}, D_{1}, D_{3}, A_{4}, A_{1}, C_{4}, C_{1}.

There is one more S_{2}-closed class which is not a clone, namely O_{7}.

3.2. Here we describe the clones in 3.1 by a generating set:

O_{1} = J_{A} (projections),
O_{4} = ⟨¬⟩ (projections and their negations),
O_{8} = ⟨c_{0}, c_{1}⟩ (constants),
O_{9} = ⟨c_{0}, c_{1}, ¬⟩ (essentially unary functions),
L_{4} = ⟨g⟩ (linear idempotent functions, g(x, y, z) := x + y + z),
L_{5} = ⟨g, ¬⟩ (linear self-dual functions),
L_{1} = ⟨c_{1}, +⟩ (all linear functions, + : (x, y) ↦ x + y),
D_{2} = ⟨h⟩ (self-dual monotone functions,
h(x, y, z) := (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)),
D_{1} = ⟨g, h⟩ (self-dual idempotent functions),
D_{3} = ⟨h, ¬⟩ (self-dual functions),
A_{4} = ⟨∧, ∨⟩ (monotone idempotent functions),
A_{1} = ⟨c_{0}, c_{1}, ∧, ∨⟩ (monotone functions),
C_{4} = ⟨∧, ∨, g⟩ (idempotent functions),
C_{1} = O_{A} (all functions).

O_{7} is the closed class generated by the constants c_{0}, c_{1}. The lattice L_{2,S_{2}} of S_{2}-clones is given in Fig. 1.

3.3. Remark. As pointed out in [10, Prop.1] there are 7 clones F among the above 14 clones for which S_{2} is not only the group of weak automorphisms but also the automorphism group (of the algebra ⟨A; F ⟩). These clones are just the S_{2}-homogeneous clones in the sense of Definition 2.1. They are D_{3}, D_{1}, D_{2}, L_{5}, L_{4}, O_{4}, O_{1} (i.e. the interval [O_{1}, D_{3}]_{L_{2,S_{2}}}, see Fig. 1) and there are no more S_{2}-homogeneous closed classes.

2In order to avoid confusion we used different fonts for the notation of closed classes defined in [15] or [14], namely e.g. S_{2}, D, O. One should notice the difference to e.g. S_{2}, O_{3}.

[figure: C_{1}; A_{1}; O_{8}; O_{7}; ∅; O_{1}; D_{2}; A_{4}; C_{4}; D_{1}; L_{4}; O_{4}; L_{5}; D_{3}; L_{1}; O_{9}; T_{2}-clones]

Figure 1: The lattice L_{2,S_{2}} (L_{2,T_{2}}) of S_{2}-clones (T_{2}-clones, resp.) and closed classes

3.4. We are going to describe all intervals S_{2}-Int(F) for Boolean clones F ≤ O_{2}. Since L_{2} is known this can be done without difficulties. Note that because of 3.1 the number of possible intervals is limited. Take some clone F and its dual F′ (= F^{s} for s = ¬) and form the interval [F ∧ F′, F ∨ F′]_{L_{2}}. Proceed as far no new intervals can be obtained. Many covering pairs, say F_{1}, F_{2} in the lattice of Fig. 1 are also covering pairs in the lattice L_{2}. In that case [F_{1}, F_{2}]_{L_{2}} cannot be an interval of the form S_{2}-Int(F), since there is no F between F_{1} and F_{2}. We list here all possible intervals [F_{1}, F_{2}] of the form

Int(F) := S_{2}-Int(F)

which are non-degenerate (i.e. F_{1} ≠ F_{2}), give one example for F (using Post’s notation^{3}) and add in parenthesis the cardinality |{F | Int(F) = [F_{1}, F_{2}]}| of clones F to which this interval corresponds.

[O_{1}, O_{8}] = Int(O_{6}) (2), [O_{8}, A_{1}] = Int(P_{6}) (2),
[A_{4}, A_{1}] = Int(A_{3}) (2), [C_{4}, C_{1}] = Int(C_{3}) (2),
[L_{4}, L_{1}] = Int(L_{3})  (2),
[D_{2}, A_{4}] = Int(F_{6}^{2}) (2), [D_{2}, C_{4}] = Int(F_{1}^{2}) (2),
[D_{2}, A_{1}] = Int(F_{3}^{2}) (2), [D_{2}, C_{1}] = Int(F_{4}^{2}) (2),
[O_{1}, A_{4}] = Int(F_{2}^{∞}) (ℵ_{0}), [O_{1}, C_{4}] = Int(F_{1}^{∞}) (ℵ_{0}),
[O_{1}, A_{1}] = Int(F_{3}^{∞}) (ℵ_{0}), [O_{1}, C_{1}] = Int(F_{4}^{∞}) (ℵ_{0}).

3with notations from 3.2 we have e.g. O_{6} = ⟨c_{0}⟩, A_{3} = ⟨∧, ∨, c_{0}⟩, L_{3} = ⟨c_{0}, g⟩, F_{6}^{2} = ⟨∧, h⟩, P_{6} = ⟨∧, c_{0}, c_{1}⟩, C_{3} = ⟨∧, c_{0}, g⟩.

The problem mentioned in 2.5, e) now can be answered: The join of G-intervals is again a G-interval and the meet of G-intervals is either empty or also again a G-interval (possibly of degenerate form [F, F] with G-clone F).

The lattice L_{3} of clones on the base set A = {0, 1, 2} is uncountable. However, as mentioned in the introduction, there are only finitely many S_{3}-clones. On the basis of [5] and [20] the following result was found by N.v. Hoa and V.V. Gorlov and proved in [14].

3.5. Theorem. There are 48 S_{3}-clones on A = {0, 1, 2}. In addition there are 4 non-empty S_{3}-closed classes which are not clones.

3.6. Remark. Among the 52 S_{3}-closed classes there are 8 non-empty S_{3}-homogeneous closed classes all of which are clones, namely

S_{2}, L_{1}S, S_{2}D_{1}, S_{2}L_{4}, S_{2}D_{2}, S_{2}O_{1}, S_{2}^{∗}D_{2}, O(= J_{3}).

This is the interval [J_{3}, S_{2}]_{L_{3,S_{3}}} (see Fig. 2).

3.7. The lattice L_{3,S_{3}} of S_{3}-clones together with the 4 S_{3}-closed classes is given in Fig. 2 ^{4}. It suffices to define explicitly the ∧-irreducible elements in the lattice L_{3,S_{3}} (17 clones and one class). All other clones (classes, resp.) are intersections of ∧-irreducibles as can be seen from Fig. 2 (where the ∧-irreducibles are marked by rectangular points). Below we list all the ∧-irreducibles since the description of all classes in [14] is given in a relatively complicated form. We introduce the following notations. Let f : A^{n} → A and a, b ∈ A (here A = {0, 1, 2}). Then f_{a,b} : {a, b}^{n} ⟶ A denotes the restriction of f to the set {a, b}. If f preserves {a, b}, then f_{a,b} : {a, b}^{n} ⟶ {a, b} will be considered as Boolean function (on the set {a, b} instead of {0, 1}). For K ⊆ O_{2} and a, b ∈ A, let K_{a,b} ⊆ O_{{a,b}} be the corresponding copy of K given by K_{a,b} = {f^{s} | f ∈ K} where s : {0, 1} → {a, b} : 0 ↦ a, 1 ↦ b and f^{s}(x_{1}, …, x_{n}) := s(f(s^{−1}(x_{1}), …, s^{−1}(x_{n}))) (cf. 1.2). We write f_{a,b} ∼ f_{0,1} if f_{a,b} = f_{0,1}^{s} for s : 0 ↦ a, 1 ↦ b. Im f denotes the image of f.

List of ∧-irreducible S_{3}-clones and S_{3}-closed classes

(1) P_{3} := O_{3} ;

(2) CL_{3} := J_{3} ∪ O_{3}^{(1)} ∪ {f | |Im f| ≤ 2} (Słupecki class);

(3) BQ_{4} := ⟨s_{1}⟩ ∪ {f | |Im f| ≤ 2} where s_{1}(x) := x + 1 (mod 3) (=permutation s_{1} = (012) ∈ S_{3});

(4) BQ_{5} := J_{3} ∪ {f | |Im f| ≤ 2};

(5) LQ := ⟨O_{3}^{(1)}⟩ ∪ F_{0}, where F_{0} is the set of all f ∈ O_{3}^{(n)} (n ∈ N) such that there are h_{1}, …, h_{n} : {0, 1, 2} → {0, 1} and h_{0} : {0, 1} → {0, 1, 2} with f(x_{1}, …, x_{n}) = h_{0}(h_{1}(x_{1}) ⊕ … ⊕ h_{n}(x_{n})) (⊕ = addition mod 2);

(6) P_{3}^{1} := ⟨O_{3}^{(1)}⟩ (essentially unary functions);

(7) Q_{2} := ⟨S_{3}⟩ (essentially unary permutations);

4Our thanks are due to B.Ganter for his help in designing this diagram. Using ”formal concept analysis”

some errors in the diagram of [14] could be detected.

[figure: (S_{3} ∪ {c_{0}, c_{1}, c_{2}})-clones; P_{3}A_{4}; P_{3}D_{2}; P_{3}O_{1}; P_{3}S^{∗}D_{2}; P_{3}(= O_{3}); P_{3}^{α}; P_{3}C_{4}; S; S_{1}; P_{3}SC_{4}; SC_{4}; SA_{4}; P_{3}SA_{4}; S_{2}; S_{2}D_{1}; S_{2}L_{4}; SD_{1}; P_{3}SD_{1}; P_{3}D_{1}; SL_{4}; P_{3}SL_{4}; P_{3}L_{4}; S_{2}O_{1}; SO_{1}; P_{3}SO_{1}; S_{2}^{∗}D_{2}; S^{∗}D_{2}; S_{2}D_{2}; SD_{2}; P_{3}SD_{2}; L_{3}; L_{5}; L_{1}S; CL_{3}; LQ; P_{3}^{1}; Q_{23}; Q_{2}; Q_{4}; BQ_{4}; LBQ_{4}; Q_{14}; Q_{34}; BQ_{5}; LBQ_{5}; Q_{15}; Q_{35}; B; LB; Q_{1}; Q_{3}; ∅; O(= J_{3})]
Figure 2: The lattice L_{3,S_{3}} of S_{3}-clones

(8) L_{3} := ⟨+, ·⟩ (clone of linear functions, +, · are addition and multiplication mod 3);

(9) S := {f | f^{s_{1}} = f} (s_{1}-self dual functions, cf.(3));

(10) S_{2} := {f | f^{s_{0}} = f and f^{s_{1}} = f}, s-self dual functions for all s ∈ S_{3}, s_{0}(x) := 2 · x (=permutation (12)) ;

(11) P_{3}^{α} := {f | f(x, …, x) = x} (idempotent functions);

(12) P_{3}C_{4} := {f | f_{a,b} ∈ C_{4,a,b} for (a, b) ∈ {(0, 1), (1, 2), (2, 0)}};

(13) P_{3}SC_{4} := {f | f ∈ P_{3}C_{4} and f_{a,b} ∼ f_{0,1} for (a, b) ∈ {(1, 2), (2, 0)}};

(14) P_{3}D_{1} := {f | f_{a,b} ∈ D_{1,a,b} for a, b ∈ {0, 1, 2}};

(15) P_{3}A_{4} := {f | f_{a,b} ∈ A_{4,a,b} for a, b ∈ {0, 1, 2}};

(16) P_{3}L_{4} := {f | f_{a,b} ∈ L_{4,a,b} for (a, b) ∈ {(0, 1), (1, 2), (2, 0)}};

(17) P_{3}S^{∗}D_{2} := {f | f ∈ P_{3}SD_{2} and (*) }, where P_{3}SD_{2} := P_{3}SC_{4} ∩ P_{3}D_{1} ∩ P_{3}A_{4} and (*) is the following property: For every g obtained from f by identification of variables (including g = f) we have: g_{0,1} ∈ J_{2} implies g ∈ J_{3}.

The S_{3}-closed classes which are not clones can be obtained from the following ∧-irreducible class B by intersection with P_{3}, LQ, P_{3}^{1} and L^{3}.

(18) B := BQ_{5} \ J_{3} = {f | |Im f| ≤ 2}.

3.8. Remarks. a) To determine the interval S_{3}-Int(F) for any concretely given clone F one can proceed as follows. Let I be the set of all ∧-irreducible clones from the list (1)–(17) in 3.7. Then

S_{3}-Int(F) = [ ⋁_{C∈T_{F}} C, ⋀_{C∈M_{F}} C]_{L_{3}}

where

M_{F} := {C ∈ I | F ⊆ C} and T_{F} := { ⋀_{D∈M′} D | M′ ⊆ I \ M_{F} , ⋀_{D∈M′} D ⊆ F }.

Instead of T_{F} one could use also the set of clones, which are ∨-irreducible in the lattice L_{3,S_{3}} and are contained in F. Analogously (using (1)–(18) in 3.7) one can determine S_{3}-Int(F) for closed classes. We shall not go into further details. As an example we mention the celebrated Janov-Muchnik-class JM_{3} generated by all functions

f_{n}(x_{1}, …, x_{n}) = \{ \begin{matrix}1 & if ∃j : x_{j} = 1 and ∀i ≠ j : x_{i} = 2 \\ 0 & otherwise. \end{matrix}

JM_{3} is a closed class with countable basis and its corresponding interval is S_{3}-Int(JM_{3}) =

[∅, B], i.e. ⋀_{s∈S_{3}} JM_{3}^{s} = ∅, ⟨ ⋁_{s∈S_{3}} JM_{3}^{s}⟩_{P_{3}} = B.

b) Because of 2.3, for G ≤ G′ ≤ S_{A}, every G′-clone is a G-clone, too. The set L_{3,S_{3}} of S_{3}- clones is finite (3.5), however there are infinitely many A_{3}-clones (A_{3} being the alternating group) as shown in [6].

4. General Galois theory for G-clones

In this section we outline a characterization of G-clones by invariant relations based on a Galois connection between operations and relations. Restricting to G-clones, all results more or less straightforward can be derived from corresponding results for arbitrary clones (see e.g. [25], [24]). Therefore we omit the proofs^{5} in this section.

4.1. For a base set A let

R_{A}^{(m)} := {ϱ | ϱ ⊆ A^{m}}

be the set of all m-ary relations and R_{A} := ⋃_{m=1}^{∞} R_{A}^{(m)}. Elements (m-tuples) r ∈ A^{m} we often

write as r = (r(1), …, r(m)), considering them as functions r : \underline{m} → A : i ↦ r(i). A function f ∈ O_{A}^{(n)} preserves the relation ϱ ∈ R_{A} (f is a polymorphism of ϱ, ϱ is invariant for f) if, for all r_{1}, …, r_{n} ∈ A^{m}, r_{1}, …, r_{n} ∈ ϱ implies f[r_{1}, …, r_{n}] ∈ ϱ where f[r_{1}, …, r_{n}] ∈ A^{m} is defined by f[r_{1}, …, r_{n}](i) := f(r_{1}(i), …, r_{n}(i)) for i ∈ \underline{m}. For F ⊆ O_{A} and Q ⊆ R_{A},

Inv_{A}F := {ϱ ∈ R_{A} | ∀f ∈ F : f preserves ϱ}

5see [13]. Some proofs in detail were also given by J.-U. Grabowski and T. Rönsch (TU Dresden).

is the set of invariant relations of F and

Pol_{A}Q := {f ∈ O_{A} | ∀ϱ ∈ Q : f preserves ϱ}

is the set of polymorphisms of G. The operators Pol-Inv give a Galois connection between functions and relations on A, and for finite A, the Galois-closed elements Pol Inv F and Inv Pol Q are just the clones and so-called relational clones: ⟨F ⟩ = Pol Inv F , [Q] = Inv Pol Q (for more details, see [25], [24]). Here Q is called a relational clone if Q = Inv Pol Q.

4.2. Definition. For s ∈ S_{A} and ϱ ∈ R_{A}^{(m)} let

ϱ^{s} := {(x_{1}^{s}, …, x_{m}^{s}) | (x_{1}, …, x_{m}) ∈ ϱ}.

(Remark: ϱ^{s} consists of all mappings \underline{m} → A of the composed form \underline{m} →^{r} A →^{s} A with r ∈ ϱ). A relational clone Q is called a relational G-clone for G ≤ S_{A}, if Q^{G} = Q (where Q^{G} := {ϱ^{s} | ϱ ∈ Q, s ∈ G}). An operation f ∈ O_{A} G-preserves ϱ if f preserves ϱ^{s} for all s ∈ G. For F ⊆ O_{A}, Q ⊆ R_{A} let

G-Pol_{A} Q := Pol_{A} Q^{G}, G-Inv_{A} F := Inv_{A} F^{G}.

In the following Lemma, (i)-(iii) describes the interplay between dualization w.r.t. s and preservation while (iv)-(v) show that the operators G-Pol and G-Inv form a Galois connection (induced by the preservation property).

4.3. Lemma. Let ϱ ∈ Q ⊆ R_{A}, f ∈ F ⊆ O_{A}, s ∈ S_{A}, G ≤ S_{A} and Q ⊆ R_{A}. Then we have: (i) f preserves ϱ iff f^{s} preserves ϱ^{s}, (ii) (Pol_{A}Q)^{s} = Pol_{A}(Q^{s}), (iii) (Inv_{A}F)^{s} = Inv_{A}(F^{s}). (iv) G-Pol Q = {f ∈ O_{A} | ∀ϱ ∈ Q : f G-preserves ϱ} and

G-Pol Q is a G-clone.

(v) G-Inv F = {ϱ ∈ R_{A} | ∀f ∈ F : f G-preserves ϱ} and G-Inv F is a relational G-clone.

Using these results one can characterize the Galois-closed sets of functions and relations (w.r.t. the above Galois connection) as follows:

4.4. Theorem. For F ⊆ O_{A}, Q ⊆ R_{A} and G ≤ S_{A} we have

(1) G-Pol G-Inv F is the G-clone generated by F:

GF = ⟨F^{G}⟩ = G-Pol G-Inv F = Pol G-Inv F,

(2) G-Inv G-Pol Q = Inv G-Pol Q is the relational G-clone generated by Q (the least relational G-clone containing Q).

Moreover, for a clone F ≤ O_{A} we have

GF = ⋂_{s∈G} F^{s} = ⋂_{s∈G} Pol Inv F^{s} = ⋂_{s∈G} Pol(Inv F)^{s}

= Pol( ⋃_{s∈G}(Inv F)^{s}) = Pol(Inv F)^{G} = G-Pol Inv F.

Combining this with 4.4(1) we get the following characterization of the lower and upper bound _{G}F and ^{G}F, resp., of G-Int F :

4.5. Proposition. Let F ≤ O_{A} be a clone and G ≤ S_{A}. Then

G-Int F = [G-Pol Inv F, Pol G-Inv F]_{L_{A}}.
□

Remark. Analogously one can define and characterize G-intervals corresponding to relational clones.

5. H-clones and H-closed classes

In this section we generalize the concept of G-clones. Instead of groups G ≤ S_{A} we use semigroups H ≤ T_{A} with unit (monoids) or without unit. However, definition 2.1 cannot be generalized canonically to H-clones. There are several possibilities (all equivalent for groups H ≤ S_{A}).

5.1. Notations. ⟨H⟩_{T_{A}} denotes the subsemigroup of T_{A} generated by H. Here

T_{A} := {h | h : A → A}

is the set of all unary mappings on A. It is a monoid w.r.t. the usual composition of mappings. Again (cf. 1.2) we write a^{h} for the image h(a) of a, composition is to read from left to right: a^{(hh′)} := (a^{h})^{h′}. Let e : x ↦ x denote the identical mapping. We write H ≤ T_{A} if H is a subsemigroup of T_{A} and H ≤_{e} T_{A} if H is a submonoid (i.e. e ∈ H ≤ T_{A}).

5.2. Definitions. Let H ⊆ T_{A} and F ⊆ O_{A} be a clone (closed class, resp.).

(a) For f, g ∈ O_{A}^{(n)}, h ∈ H we write

g \overrightarrow{→}^{h}f

if ∀x_{1}, …, x_{n} ∈ A : (g(x_{1}, …, x_{n}))^{h} = f(x_{1}^{h}, …, x_{n}^{h}), i.e. if the following diagram commutes

[figure: A^{n}; A^{n}; A; A; h^{[n]}; h; f; g]

(where h^{[n]} is defined componentwise). We write g \begin{matrix}⇝ \\ ⇝ \end{matrix}^{h}f if there exists a chain g \overrightarrow{→}^{h}g_{1} \overrightarrow{→}^{h} … \overrightarrow{→}^{h}g_{m−1} \overrightarrow{→}^{h}f, and g \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} f if in addition all g_{i} (i = 1, …, m − 1) belong to F. A function f is called h-homogeneous if f \overrightarrow{→}^{h}f and weakly h-homogeneous (in F) if f \begin{matrix}⇝ \\ ⇝ \end{matrix}^{h}f (f \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} f), respectively.

(b) F is called right H-clone (H-closed class, resp.) if for all h ∈ H we have

∀f ∈ F ∃g ∈ F : g \overrightarrow{→}^{h}f. (*)

For short, right H-clones will be called H-clones. F is called left H-clone (H-closed class, resp.) if for all h ∈ H we have

∀f ∈ F ∃g ∈ F : f \overrightarrow{→}^{h}g. (**)

(c) F is called H-homogeneous (right) H-clone if

∀f ∈ F ∃g ∈ F ∀h ∈ H : g \overrightarrow{→}^{h}f.

Analogously one defines H-homogeneous left H-clones.^{6}

(d) Let L_{A,H} (L′_{A,H}, resp.) denote the set of all H-clones F ≤ O_{A} (closed classes, resp.).

5.3. Examples. 1) J_{A} is an H-homogeneous H-clone for every H ≤ T_{A}.

2) For given H ≤ T_{A}, the set \{g ∈ O_{A} | ∀h ∈ H : g \overrightarrow{→}^{h}g\} is the largest clone F for which all h ∈ H are endomorphisms (of the algebra ⟨A; F ⟩) and it is an H-clone.

3) For e ∈ H, right and left H-homogeneous H-clones coincide (note g \overrightarrow{→}^{e}f implies g = f), and F is an H-homogeneous H-clone iff ∀f ∈ F ∀h ∈ H : f \overrightarrow{→}^{h}f. In particular, for |A| = k = 2 and H = T_{2} we have: F is a T_{2}–homogeneous (right=left) T_{2}–clone iff F ≤ D_{1}.

4) Note that g \overrightarrow{→}^{c}f means for some constant c, that c = f(c, …, c). Thus, for |A| = k = 2 and H = {c_{0}, c_{1}}, a clone F is an H–homogeneous clone iff every f ∈ F is idempotent (f(0, …, 0) = 0 and f(1, …, 1) = 1), i.e. F ≤ C_{4}. On the other hand, a clone F is a left H-homogeneous H-clone if, by definition,

∀ f ∈ F ∃ g ∈ F : 0 = g(0, …, 0) ∧ 1 = g(1, …, 1).

Since g = e_{1}^{1} ∈ F fulfils this condition, every clone is an H- homogeneous left H-clone.

5.4. Remarks.

(a) For a permutation s ∈ S_{A} with g \overrightarrow{→}^{s}f, the function f uniquely determines g (and vice versa), namely we have g \overrightarrow{→}^{s}f ⟺ g^{s} = f. Consequently, for H = G ⊆ S_{A}, both definitions, 5.2b) and 2.1 coincide and left H-clones agree with right H-clones, they are just the G-clones in the sense of 2.1. Moreover, in that case, a clone is left H-homogeneous iff it is right H-homogeneous iff it is G-homogeneous (cf. 2.1).

(b) Obviously, H-homogeneous H-clones are H-clones since the property in 5.2(c) implies (*) in 5.2(b).

(c) For an algebra A with F as clone of term operations, mappings h ∈ T_{A} with the property 5.2(*) (in several modifications) were intensively studied by K. Głazek (cf. e.g. [9]) as semi-weak endomorphisms, cf. also [7, 3.4]).

(d) A simple but useful observation is: For H′ ⊆ H, every H-closed class is H′-closed, too. Moreover, a class F is H′ ∪ H′′-closed iff it is both, H′-closed and H′′-closed. In particular, F is an H-clone iff it is an {h}-clone for every h ∈ H. In 5.6 we shall see that F is an H-clone iff it is an ⟨H⟩_{T_{A}}-clone.

(e) Let g_{0} \overrightarrow{→}^{h}g_{1} \overrightarrow{→}^{h} … \overrightarrow{→}^{h}g_{m}. This situation implies the following properties:

(i) g_{0} preserves ker h, ker h^{2},…,ker h^{m},

(ii) g_{m} preserves Im h, Im h^{2},…,Im h^{m}.

In fact, e.g. g_{0}(x_{1}, …, x_{n})^{h} = g_{1}(x_{1}^{h}, …, x_{n}^{h}) implies g_{0} ∈Pol ker h and g_{m}(x_{1}^{h}, …, x_{n}^{h}) = g_{m−1}(x_{1}, …, x_{n})^{h} implies g_{m} ∈ Pol Im h (analogously for h^{2}, …, h^{m}).

6For |H| = 1, right (left) H-homogeneous clones are just the right (left) H-clones.

(f) Let F_{1}(H) := F_{1} := ⋂_{h∈H} Pol_{A}Im(h) be the set of all functions preserving every image

Im h. Because of (ii) above, every H-clone is contained in F_{1}(H). However, in general, F_{1} is not an H-clone (cf. also 5.11 and 5.12). To see this, let A = {0, 1, 2}, H := ⟨h_{1}, h_{2}, h⟩ where 0^{h_{1}} = 2^{h_{1}} = 0, 1^{h_{1}} = 1, 0^{h_{2}} = 2^{h_{2}} = 2, 1^{h_{2}} = 1, 0^{h} = 2^{h} = 1, 1^{h} = 0. Then the constant f := c_{1}^{1} ∈ O_{A}^{(1)} belongs to F_{1}(H), but no g ∈ F_{1} satisfies g \overrightarrow{→}^{h}f, because g(1)^{h} = f(1^{h}) = f(0) = 1 would imply g(1) ∈ h^{−1}(1) = {0, 2} in contradiction to g(1) ∈ Im h_{1} ∩ Im h_{2} = {1}.

The following results are formulated for H-clones, but they can be used analogously for arbitrary closed classes. If not otherwise stated, H always denotes a subset of T_{A} for a finite set A.

5.5. Lemma. Let g_{i}, f_{i} ∈ O_{A}^{(n)} and g_{i} \overrightarrow{→}^{h}f_{i} for i = 1, 2. Then we have (σg_{1}) \overrightarrow{→}^{h}(σf_{1}) for every operator σ ∈ \{τ, ζ, Δ, ∇\} and (g_{1} ∗ g_{2}) \overrightarrow{→}^{h}(f_{1} ∗ f_{2}).

Proof. The first part immediately follows from the definitions. The second part follows from

g_{1}(g_{2}(x_{1}, …, x_{m}), …, x_{m+n−1})^{h} = f_{1}(g_{2}(x_{1}, …, x_{m})^{h}, …, x_{m+n−1}^{h})
= f_{1}(f_{2}(x_{1}^{h}, …, x_{m}^{h}), …, x_{m+n−1}^{h}). □

The following Theorem provides a criterion for H-clones based on generating sets and will be useful for the construction of H-clones.

5.6. Theorem. Let H = ⟨H_{0}⟩_{T_{A}} ≤ T_{A} and F = ⟨F_{0}⟩_{O_{A}} ≤ O_{A} with generating sets H_{0} and F_{0}. Then the clone F ≤ O_{A} is an H-clone iff

∀ h ∈ H_{0} ∀ f ∈ F_{0} ∃ g ∈ F : g \overrightarrow{→}^{h}f (^{∘})

In particular, F is an H-clone iff F is an H_{0}-clone.

Proof. Obviously we have to prove the “if”-part only. At first we proceed by induction on the generation of F from F_{0}. By Lemma 5.5 we conclude from (^{∘}) that

∀ h ∈ H_{0} ∀ f ∈ ⟨F_{0}⟩ ∃ g ∈ F : g \overrightarrow{→}^{h}f (^{∘∘})

Secondly, let h_{1}, h_{2} ∈ H_{0}, f ∈ F. Then, by (^{∘∘}) there exists g_{2} ∈ F with g_{2} \overrightarrow{→}^{h_{2}}f, and for g_{2} there exists g_{1} ∈ F such that g_{1} \overrightarrow{→}^{h_{1}}g_{2}. Then

g_{1}(x_{1}, …, x_{n})^{h_{1}h_{2}} = (g_{2}(x_{1}^{h_{1}}, …, x_{n}^{h_{1}}))^{h_{2}} = f(x_{1}^{h_{1}h_{2}}, …, x_{n}^{h_{1}h_{2}}),

i.e. g_{1} \overrightarrow{→}^{h_{1}h_{2}}f and the property (^{∘∘}) extends to the closure ⟨H_{0}⟩=H. Thus F is H-closed. □

5.7. Remark. Every H ≤ T_{A} splits into the “group part” G := H ∩ S_{A} and the “pure semigroup part” H′ := H \ G (note that H′ ≤ T_{A} for finite A). By 5.6 these parts can be treated separately (e.g. using generating systems).

The identity plays no role for H-clones. Since f \overrightarrow{→}^{e}f we have:

5.8. Lemma. A clone F is an H-clone iff it is an (H \ {e})-clone.

Let us look now for intersections and unions of H-clones.

5.9. Lemma. For h ∈ T_{A}, a set H ⊆ T_{A} and a clone F ≤ O_{A} let

γ_{1}(F) := \{f ∈ F | ∃g ∈ F : g \overrightarrow{→}^{h}f\},
γ_{n+1}(F) := γ_{1}(γ_{n}(F)), n = 1, 2, 3, …,
γ_{{h}}(F) := ⋂_{n=1}^{∞} γ_{n}(F),
γ_{H}(F) := ⋂_{h∈H} γ_{{h}}(F).

Then

(a) γ_{1}(F) is a clone contained in F.

(b) γ_{{h}}(F) is an {h}-clone contained in F.

(c) γ_{H}(F) is an H-clone contained in F.

Proof. (a) directly follows from Lemma 5.5. Thus also γ_{{h}}(F) and therefore γ_{H}(F) are clones. In order to prove (b) let f ∈ γ_{{h}}(F) be an m-ary function. By definition f ∈ γ_{n}(F), i.e., for every n ∈ N there exists g_{n} ∈ γ_{n}(F)^{(m)} such that g_{n} \overrightarrow{→}^{h}f. Consider the sequence (g_{n})_{n∈N}. Since O_{A}^{(m)} is finite there is some n_{0} ∈ N such that g_{n_{0}} appears infinitely many often among g_{1}, g_{2}, g_{3}, . . .. Therefore g_{n_{0}} ∈ γ_{n}(F) for all n ≥ n_{0} and we have g_{n_{0}} ∈ γ_{{h}}(F) (note that the γ_{n}(F) form a descending chain). Now g_{n_{0}} \overrightarrow{→}^{h}f shows that γ_{\{h\}}(F) is an \{h\}-clone.

(c) follows from the definitions and 5.4(d). □

5.10. Theorem. Let H ⊆ T_{A}.

(1) Let F ≤ O_{A} be a clone. Then γ_{H}(F) is the greatest H-clone contained in F.

(2) The join (in L_{A}) F ∨G = ⟨F ∪G⟩_{O_{A}} of H-clones F, G is again an H-clone (analogously for H-homogeneous H-clones).

(3) L_{A,H} is a lattice w.r.t. inclusion with least element J_{A} and greatest element γ_{H}(O_{A}). The corresponding join ∨ and meet ∧_{H} are given by

F ∨ G = ⟨F ∪ G⟩_{O_{A}} and
F ∧_{H} G = γ_{H}(F ∧ G).

Proof. (1): Let F′ be an H-clone contained in F. Then F′ = γ_{{h}}(F′) ⊆ γ_{{h}}(F) for h ∈ H, hence F′ ⊆ γ_{H}(F) and, by Lemma 5.9(c), γ_{H}(F) is the largest H-clone contained in F. (2): The proof of (2) immediately follows from 5.6. (3): By (1), F ∧_{H} G is the largest H-clone contained in both, F and G. □

We ask for a more explicite description of γ_{H}(F), in particular for the largest H-clone γ_{H}(O_{A}). This will be answered by the next two propositions. Because of the definition of γ_{H}(F) (5.9), it suffices to consider the case H = {h} only.

5.11. Proposition. Let h ∈ T_{A} and F ≤ O_{A}. Then we have

γ_{\{h\}}(F) = \{f ∈ F | ∃g ∈ F : g \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} g and g \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} f\}.

Proof. Let R denote the right side of the above equation and let f_{0} := f be an element of γ_{\{h\}}(F), the greatest \{h\}-clone contained in F. Thus there exist f_{1} ∈ γ_{\{h\}}(F) with f_{1} \overrightarrow{→}^{h}f_{0} and, by induction, there are f_{i} ∈ γ_{\{h\}}(F) with f_{i+1} \overrightarrow{→}^{h}f_{i} (i ≥ 0). Since all f_{i} are of the same arity as f, the set {f_{i} | i ∈ N} is finite and there must exist r, m ∈ N with f_{r+m} = f_{r} =: g. Thus g \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} g and g \begin{matrix}⇝ \\ ⇝ \end{matrix}_{F}^{h} f, consequently f ∈ R. Conversely, let f ∈ R, i.e., there is a chain

g = f_{r+m} \overrightarrow{→}^{h}f_{r+m−1} \overrightarrow{→}^{h} … \overrightarrow{→}^{h}f_{r} = g \overrightarrow{→}^{h}f_{r−1} \overrightarrow{→}^{h} … f_{1} \overrightarrow{→}^{h}f_{0} = f

(with f_{i} ∈ F). Then the infinite sequence (f_{i})_{i∈N} with f_{r+l+km} := f_{r+l} for l ∈ {0, 1, …, m−1}, k ∈ N, satisfies f_{i+1} \overrightarrow{→}^{h}f_{i} for all i ∈ N. Consequently, f_{i} ∈ γ_{\{h\}}(F), in particular f = f_{0} ∈ γ_{{h}}(F). □

Note that 5.11 characterizes in particular the largest {h}-clone γ_{{h}}(O_{A}). Having this in mind we look for a characterization of weakly h-homogeneous functions (cf. 5.2(a)).

5.12. Proposition. (1) A function g ∈ O_{A}^{(n)} is weakly h-homogeneous (i.e. g \begin{matrix}⇝ \\ ⇝ \end{matrix}^{h}g) iff there exists m ∈ N such that the following three conditions hold:

(i) g is h^{m}-homogeneous, (ii) g preserves ker h, ker h^{2}, …, ker h^{m}, (iii) g preserves Im h, Im h^{2}, …, Im h^{m}.

(2) Let h ∈ T_{A} be idempotent. Then the largest {h}-clone is γ_{{h}}(O_{A}) = Pol Im h.

Proof. (1): Let g be weakly h-homogeneous, i.e. we have g \overrightarrow{→}^{h}g_{1} \overrightarrow{→}^{h} … \overrightarrow{→}^{h}g_{m−1} \overrightarrow{→}^{h}g for suitable m and g_{i}. Then g satisfies (ii) and (iii) because of 5.4(e). Moreover, g(x_{1}, …, x_{n})^{h^{m}} = g_{1}(x_{1}^{h}, …, x_{n}^{h})^{h^{m−1}} = … = g_{m−1}(x_{1}^{h^{m−1}}, …, x_{n}^{h^{m−1}})^{h} = g(x_{1}^{h^{m}}, …, x_{n}^{h^{m}}), i.e. (i) also holds. Conversely, let g satisfy (i) – (iii) and put g_{0} := g_{m} := g. We define g_{1}, …, g_{m−1} as follows:

g_{i+1}(x_{1}^{h^{i+1}}, …, x_{n}^{h^{i+1}}) := g_{i}(x_{1}^{h^{i}}, …, x_{n}^{h^{i}})^{h}, i = 0, 1, , …, m − 2.

Because of (ii), g_{1}, g_{2}, …, g_{m−1} are well-defined on Im h, Im h^{2}, …, Im h^{m−1}, respectively. The remaining values are chosen arbitrary but according to the following conditions:

g_{i}(y_{1}, …, y_{n}) ∈ h^{−1}(g_{i+1}(y_{1}^{h}, …, y_{n}^{h})) for (y_{1}, …, y_{n}) ∈ A^{n} \ (Im h^{i})^{n},

i = 1, …, m − 1. Such values really exist according to (iii). Then, by definition, we have g_{i} \overrightarrow{→}^{h}g_{i+1} for i = 0, 1, …, m − 2. Moreover, we also have g_{m−1} \overrightarrow{→}^{h}g. In fact, g_{m−1}(y_{1}, …, y_{n})^{h} = g(y_{1}^{h}, …, y_{n}^{h}) for (y_{1}, …, y_{n}) ∈ A^{n} \(Im h^{m−1})^{n} by definition, and for (y_{1}, …, y_{n}) = (x_{1}^{h^{m−1}}, …, x_{n}^{h^{m−1}}) ∈ (Im h^{m−1})^{n} we have g_{m−1}(x_{1}^{h^{m−1}}, …, x_{n}^{h^{m−1}})^{h} = g_{m−2}(x_{1}^{h^{m−2}}, …, x_{n}^{h^{m−2}})^{h^{2}} = …

… = g_{0}(x_{1}, …, x_{n})^{h^{m}} =_{(i)} g(x_{1}^{h^{m}}, …, x_{n}^{h^{m}}).

Thus g \overrightarrow{→}^{h}g_{1} \overrightarrow{→}^{h} … \overrightarrow{→}^{h}g_{m−1} \overrightarrow{→}^{h}g, i.e. g is weakly h-homogeneous. (2): By 5.4(e) and 5.11 we have γ_{{h}}(O_{A}) ⊆ Pol Im h. Let f ∈ Pol Im h. Because of hh = h we have x^{h} = x for x ∈ Im h, thus (f(x_{1}^{h}, …, x_{n}^{h}))^{h} = f(x_{1}^{h}, …, x_{n}^{h}), i.e. h^{[n]}fh = h^{[n]}f (cf. also 5.2). Consequently, for g := h^{[n]}f we have gh = h^{[n]}fh = h^{[n]}f = h^{[n]}h^{[n]}f, i.e. g \overrightarrow{→}^{h}g \overrightarrow{→}^{h}f. Obviously, g ∈ Pol Im h, thus f ∈ γ_{\{h\}}(O_{A}) by 5.11. □

In general, the intersection of H-clones might not be an H-clone. However, H-homogeneous clones are closed w.r.t. intersections:

5.13. Proposition. Assume e ∈ H. Then we have:

(a) For an H-homogeneous H-clone F, every f ∈ F is an H-homogeneous function.

(b) The intersection F ∧ G of H-homogeneous H-clones F and G is an H-homogeneous H-clone.

Proof. (a) directly follows from the definitions (5.2, note g \overrightarrow{→}^{e}f ⟺ g = f). Now (b) follows from (a) (use g = f in 5.2(c)). □

6. H-clones and H-closed classes on A = {0, 1} and A = {0, 1, 2}

A) The case A = {0, 1}

6.1. On the 2-element set 2 = {0, 1} there are 4 unary mappings (e, ¬, c_{0}, c_{1}) and 9 nonempty subsemigroups of T_{2}, three of which do not contain the identity e and need not to be considered in connection with H-clones because of 5.8. The lattice of subsemigroups is given in Fig. 3.

[figure: T_{2}; S_{2}; {e, c_{1}}; {e, c_{0}}; {c_{1}}; {c_{0}}; ∅; {e}; {e, c_{0}, c_{1}}; {c_{0}, c_{1}}]

Figure 3: The subsemigroup lattice of T_{2}

We are going to determine the H-closed classes for all H ≤ T_{2}. Obviously H = {e} gives Post’s lattice L_{2,H} = L_{2} of all clones (which we do not want to give here (cf. e.g. [15], [25]). For H = S_{2} the lattice L_{2,S_{2}} is given in Fig. 1 (page 188).

We shall indicate the case dealing with right H-clones by R , the left H-clone case by L , and analogously RH (and LH ) if we consider right (left) H-homogeneous clones.

6.2. The case H = {c_{0}} (and H = {c_{1}}). R : For H = {c_{0}} (or, equivalently H = {e, c_{0}}), cf. 5.8), Definition 5.2b immediately gives (note g \overrightarrow{→}^{c_{0}}f ⟺ 0 = f(0, …, 0)):

F ≤ O_{2} is {c_{0}}-closed iff F ≤ C_{3} := {f | f(0, …, 0) = 0}.

Analogously, F ≤ O_{2} is {c_{1}}-closed iff F ≤ C_{2} := {f | f(1, …, 1) = 1}. L : By Definition 5.2b, F ≤ O_{2} is left {c_{0}}-closed iff F ∩ C_{3} ≠ ∅. Thus every clone is a left {c_{0}}-clone and every non-empty closed class except O_{2} := {c_{1}} is left {c_{0}}-closed. (Analogous results hold for H = {c_{1}} (with O_{3} := {c_{1}} instead of O_{2}.) RH LH : As remarked above (footnote in 5.2) these cases coincide with R and L .

6.3. The case H = {c_{0}, c_{1}}. R : By 6.2 (cf. also 5.3(4)) we have F ≤ O_{2} is {c_{0}, c_{1}}-closed (equivalently, {e, c_{0}, c_{1}}-closed) iff F ≤ C_{4} = C_{2} ∩ C_{3} (cf. 3.2). L : By 6.2 we have: F ≤ O_{2} is left {c_{0}, c_{1}}-closed iff F ∩ C_{3} ≠ ∅ and F ∩ C_{2} ≠ ∅. Thus every clone is a left {c_{0}, c_{1}}-clone and every non-empty closed class except O_{2} and O_{3} is left {c_{0}, c_{1}}-closed. RH : Right {c_{0}, c_{1}}-homogeneous closed classes are clones, since they contain with some idempotent function also the identity. Due to 5.3(4), a clone F is {c_{0}, c_{1}}-homogeneous iff F ≤ C_{4}. LH : By 6.2 we get: F is left {c_{0}, c_{1}}-homogeneous iff F ∩ C_{2} ∩ C_{3} ≠ ∅. Thus again, every clone is left {c_{0}, c_{1}}-homogeneous (see also 5.3(4)) and every closed class except O_{7}, O_{2} and O_{3} is left {c_{0}, c_{1}}-homogeneous.

Thus the lattices L_{2,{c_{0}}}, L_{2,{c_{1}}}, L_{2,{c_{0},c_{1}}} are special parts of Post’s lattice L_{2}. All these parts are infinite.

6.4. Remark. If one considers H ∪ {e} instead of H in the cases 6.2 and 6.3 then, according to 5.8, nothing changes for clones. Changes appear only in case of left H-homogeneous clones which coincide with the right one’s (cf. 5.3(3)).

6.5. The case H = T_{2}. R : With 6.2 (and 5.4d) one easily checks: F ≤ O_{2} is T_{2}-closed iff F is S_{2}-closed and F ≤ C_{4} (i.e. every function is idempotent). Thus L_{2,T_{2}} is the part of Fig. 1 (page 188) consisting of clones below C_{4}, i.e. the six T_{2}-clones O_{1}, D_{2}, D_{1}, L_{4}, A_{4}, C_{4}. L The set of left T_{2}-clones differs from the set of the just described (right) T_{2}-clones. F ≤ O_{2} is a left T_{2}-clone (cf. 5.2b) iff F is a (left=right, cf. 5.4(a)) S_{2}-clone and a left {c_{0}, c_{1}}-clone. Thus, by 6.3, left T_{2}-clones and S_{2}-clones coincide. By 5.3(3), RH = LH , and the T_{2}-homogeneous clones F are those with F ≤ D_{1}.

All results are collected in Table 1 at the end of this paper.

B) The case A = {0, 1, 2}

We shall consider here only two subsemigroups H both containing S_{3}, namely H_{C} := S_{3} ∪ {c_{0}, c_{1}, c_{2}} and T_{3} (for H = S_{3} see 3.5, 3.6). Moreover, we shall restrict to the case R of (right) H-clones only (however the cases L , LH and RH are also included in Table 1).

6.6. H_{C}-clones. F is an H_{C}-clone iff it is an S_{3}-clone with the additional property of being a {c_{0}, c_{1}, c_{2}}- clone, i.e. ∀ f ∈ F ∃ g_{0}, g_{1}, g_{2} ∈ F : g_{i} \overrightarrow{→}^{c_{i}}f (i.e. explicitly c_{i} = f(c_{i}, …, c_{i}), i ∈ \{0, 1, 2\}). Consequently, every f ∈ F must be idempotent and we have (note that P_{3}^{α} denotes the clone of idempotent functions):

L_{3,H_{C}} = {F | F ∈ L_{3,S_{3}} and F ≤ P_{3}^{α}},

cf. Fig. 2 on page 190.

We are going to describe T_{3}-clones. Obviously, every T_{3}-clone F is an S_{3}-clone as well as an H_{C}-clone, in particular F ≤ P_{3}^{α} due to 6.6. Moreover, T_{3} = ⟨S_{3} ∪ {h_{0}}⟩_{T_{3}} for every h_{0} : A → A with |Im h_{0}| = |A|−1 = 2. Thus, by 5.6 we get:

6.7. Lemma. A clone F ≤ O_{3} is a T_{3}-clone iff F ≤ P_{3}^{α} and F satisfies

∀ f ∈ F ∃ g ∈ F : g \overrightarrow{→}^{h_{0}}f (*)

i.e. (g(x_{1}, …, x_{n}))^{h_{0}} = f(x_{1}^{h_{0}}, …, x_{n}^{h_{0}}) for all x_{1}, …, x_{n} ∈ A, n = ar f and some h_{0} ∈ T_{3}, |Im h_{0}| = 2. □

With notations from 3.7 idempotency and condition (*) for all such h_{0} imply f ∈ P_{3}C_{4}. Due to 5.10(2) we can restrict our attention to T_{3}-clones below P_{3}C_{4} which are ∨-irreducible in the lattice of T_{3}-clones. Thus, in order to determine all T_{3}-clones we firstly determine the ∨-irreducible (in L_{3,S_{3}}) S_{3}-clones F (from 3.7) with F ≤ P_{3}C_{4} and (*) (e.g. using h_{0} : x ↦ x^{2} (mod 3)). It turns out that only one of the 9 ∨-irreducible S_{3}-clones F ≤ P_{3}C_{4} is not a T_{3}-clone (namely S_{2}L_{4}, cf. Fig. 2).

6.8. Lemma. Among the ∨-irreducible S_{3}-clones there are exactly the following 8 T_{3}-clones F ≤ P_{3}C_{4} (notations see 5.3 and Fig. 2):

S_{2}^{∗}D_{2} := S_{2} ∧ P_{3}S^{∗}D_{2}
S^{∗}D_{2} := S ∧ P_{3}S^{∗}D_{2}
P_{3}S^{∗}D_{2}
S_{2}O_{1} := S_{2} ∧ P_{3}L_{4} ∧ P_{3}A_{4}
SO_{1} := S ∧ P_{3}L_{4} ∧ P_{3}A_{4}
P_{3}SO_{1} := P_{3}SC_{4} ∧ P_{3}L_{4} ∧ P_{3}A_{4}
P_{3}O_{1} := P_{3}L_{4} ∧ P_{3}A_{4}.

We delete the technical proof.

Now there remain a few more clones which are candidates for a ∨-irreducible (now in L_{3,T_{3}}!) T_{3}-clone, namely (with notations from Fig. 2) the clones SL_{4}, SD_{1}, P_{3}SL_{4}, SC_{4}, P_{3}SC_{4}, P_{3}SA_{4}, P_{3}A_{4}. However, among these there are only two T_{3}-clones, namely P_{3}SL_{4} and P_{3}A_{4} (the others are not T_{3}-clones).

Thus all possible unions of the T_{3}-clones in Lemma 6.8 together with P_{3}SL_{4} and P_{3}SA_{4} give the set of all T_{3}-clones. We describe them also in terms of ∧-irreducible clones using the list in 3.7.

6.9. Proposition. There are 18 T_{3}-clones, the 8 clones from Lemma 6.8 and the following 10 T_{3}-clones:

S_{2}D_{2} := S_{2}O_{1} ∨ S_{2}^{∗}D_{2}  = S_{2} ∧ P_{3}D_{1} ∧ P_{3}A_{4},
SD_{2} := SO_{1} ∨ S^{∗}D_{2}  = S ∧ P_{3}D_{1} ∧ P_{3}A_{4}
P_{3}SD_{2} := P_{3}SO_{1} ∨ P_{3}S^{∗}D_{2}  = P_{3}SC_{4} ∧ P_{3}D_{1} ∧ P_{3}A_{4},
P_{3}D_{2} := P_{3}O_{1} ∨ P_{3}S^{∗}D_{2}  = P_{3}D_{1} ∧ P_{3}A_{4},
P_{3}SL_{4} :=  = P_{3}SC_{4} ∧ P_{3}L_{4},
P_{3}L_{4} := P_{3}SL_{4} ∨ P_{3}O_{1},
P_{3}SD_{1} := P_{3}SL_{4} ∨ P_{3}S^{∗}D_{2}  = P_{3}SC_{4} ∧ P_{3}D_{1},
P_{3}D_{1} = P_{3}SL_{4} ∨ P_{3}S^{∗}D_{2} ∨ P_{3}O_{1},

P_{3}A_{4},

P_{3}C_{4} = P_{3}SL_{4} ∨ P_{3}A_{4}.

That part of Fig. 2 which represents the lattice L_{3,T_{3}} of T_{3}-clones is given in Fig. 4. Table 1 below contains the results of this section with some additional information.

[figure: P_{3}A_{4}; P_{3}D_{2}; P_{3}O_{1}; P_{3}S^{∗}D_{2}; P_{3}C_{4}; P_{3}SD_{1}; P_{3}D_{1}; P_{3}SL_{4}; P_{3}L_{4}; S_{2}O_{1}; SO_{1}; P_{3}SO_{1}; S_{2}^{∗}D_{2}; S^{∗}D_{2}; S_{2}D_{2}; SD_{2}; P_{3}SD_{2}; O(= J_{3})]
Figure 4: The lattice L_{3,T_{3}} of T_{3}-clones

H R : (right) H-clones F L : left H-clones F RH : right H-homogeneous clones F LH : left H-homogeneous clones F

k = 2
{c_{0}}  F ≤ C_{3}  L_{2} (all clones)  F ≤ C_{3}  L_{2} (all clones)
{c_{1}}  F ≤ C_{2}  L_{2} (all clones)  F ≤ C_{2}  L_{2} (all clones)
{c_{0}, c_{1}}  F ≤ C_{4}  L_{2} (all clones)  F ≤ C_{4}  L_{2} (all clones)
{e, c_{0}}  F ≤ C_{3}  L_{2} (all clones)  F ≤ C_{3}  F ≤ C_{3}
{e, c_{1}}  F ≤ C_{2}  L_{2} (all clones)  F ≤ C_{2}  F ≤ C_{2}
{e, c_{0}, c_{1}}  F ≤ C_{4}  L_{2} (all clones)  F ≤ C_{4}  F ≤ C_{4}
S_{2} (Fig. 1)  L_{2,S_{2}}  L_{2,S_{2}}  [O_{1}, D_{3}]_{L_{2,S_{2}}}  [O_{1}, D_{3}]_{L_{2,S_{2}}}
T_{2} (Fig. 1)  L_{2,T_{2}}  L_{2,T_{2}}  [O_{1}, D_{1}]_{L_{2,T_{2}}}  [O_{1}, D_{1}]_{L_{2,T_{2}}}
k = 3
S_{3} (Fig. 2)  L_{3,S_{3}}  L_{3,S_{3}}  [J_{3}, S_{2}]_{L_{3,S_{3}}}  [J_{3}, S_{2}]_{L_{3,S_{3}}}
H_{C} (Fig. 2) [J_{3}, P_{3}^{α}]_{L_{3,S_{3}}}  L_{3,S_{3}}  [J_{3}, S_{2}]_{L_{3,S_{3}}}  [J_{3}, S_{2}]_{L_{3,S_{3}}}
T_{3} (Fig. 4, 2)  L_{3,T_{3}}  [J_{3}, Q_{35}]_{L_{3,S_{3}}}  J_{3}  J_{3}
Table 1: H-clones for all H ≤ T_{2} and some H ≤ T_{3}

References

[1] Bulatov, A.; Krokhin, A.; Safin, K.; Sukhanov,E.: On the structure of clone lattices. In: K. Denecke, O. Lüders (eds.), General Algebra and Discrete Mathematics, Heldermann-Verlag Berlin 1995, 27–34.

[2] Burle, G. A.: Classes of k-valued logic containing all unary functions (Russian). Diskret. Analiz 10 (1967), 3–7.

[3] Csákány, B.; Gavalcova, T.: Finite homogeneous algebras I. Acta Sci. Math. (Szeged) 42 (1980), 57–65.

[4] Demetrovics, J.; Hannák, L.: On the cardinality of self-dual closed classes in k-valued logics. Közl.-MTA Számitástech. Aut. Kutató Int. Budapest 23 (1979), 7–17.

[5] Demetrovics, J.; Hannák, L.; Marchenkov, S. S.: On closed classes of self-dual functions in P_{3}. Colloq. Math. Soc. Janos Bolyai 28. Finite Algebra and Multiple-Valued Logic Szeged (Hungary) 1979, 183–189.

[6] Demetrovics, J.; Hannák, L.; Marchenkov, S. S.: On closed classes of self-dual functions in P_{3}. Metodi diskretnogo analiza v reshenii kombinatornych zadach. Sbornik trudov Instituta Matematiki SO Akademii Nauk SSSR, 34 (1980), 38–73.

[7] Denecke, K.; Lau, D.; Pöschel, R.; Schweigert, D.: Hyperidentities, hyperequational classes and clone congruences. In: Contributions to General Algebra 7, Wien 1991, 87–118.

[8] Głazek, K.: Weak homomorphisms of general algebras and related topics. Math. Seminar Notes 8 (1980), 1–36.

[9] Głazek, K.: Semigroups of weak endomorphisms of universal algebras. Proc. Intern. Symp. on Semigroup Theory and its related fields, Kyoto (Aug. 30 - Sept. 1), Japan, 1990, 85–102.

[10] Głazek, K.: On weak automorphisms of some finite algebras. Contemp. Math. 131 (1992), 99–110.

[11] Goetz, A.: On weak isomorphisms and weak homomorphisms of abstract algebras. Colloq. Math. 14 (1966), 163–167.

[12] Gorlov, V. V.; Lau, D.: Über Automorphismen auf Funktionenalgebren. Rostock. Mathem. Kolloq. 23 (1983), 35–42.

[13] Gorlov, V. V.; Pöschel, R.: Clones closed with respect to permutation groups or transformation semigroups. Preprint MATH-AL-2-1995, TU Dresden, July 1995.

[14] Nguen van Hoa: On the structure of self-dual closed classes of three-valued logic P_{3} (Russian). Diskretn. Mathematika 4 4 (1992), 82–95.

[15] Jablonski, S. W.; Gawrilow, G. P.; Kudrjawzew, W. B.: Boolesche Funktionen und Postsche Klassen. Akademie-Verlag, Berlin 1970.

[16] Janov, I.; Muchnik, A. A.: On the existence of k-valued closed classes without a finite basis. (Russian) Dokl. Akad. Nauk SSSR 127 (1959), 44–46.

[17] Kuznetsov, A. V.: Structures with closure and criteria for functional completeness (Russian). Uspechi Matem. Nauk 16 (98) (1961), 201–202.

[18] Lau, D.: Über abgeschlossene Mengen linearer Funktionen in mehrwertigen Logiken. J. Inf. Process. Cybern. EIK 24 (1988), 367–381.

[19] Mal’cev, A. I.: Iterative algebras and Post’s varieties. (Russian). Algebra i Logika 5 (1966), 5–24.

[20] Marchenkov, S. S.: On closed classes of self-dual functions of multiple-valued logic. (Russian). Problemy Kibernetiki 36, 5–22.

[21] Marchenkov, S. S.: S-classification of idempotent algebras with finite carrier. (Russian). Doklady Akad. Nauk 348 5 (1996), 587–589.

[22] Marczewski, E.: Independence and homomorphisms in abstract algebras. Fund. Math. 50 (1961), 45–61.

[23] McKenzie, R. N.; McNulty, G. F.; Taylor, W. F.: Algebras, lattices, varieties. Vol. I. Wadsworth & Brooks, Belmont, California 1987.

[24] Pöschel, R.: A general Galois theory for operations and relations and concrete characterization of related algebraic structures. Report R-01/80, ZIMM, AdWdDDR, Berlin 1980.

[25] Pöschel, R.; Kalužnin, L.A.: Funktionen- und Relationenalgebren. VEB Deutscher Verlag der Wissenschaften, Berlin 1979. Birkhäuser Verlag, Basel and Stuttgart 1979.

[26] Pöschel, R.: Cryptomorphisms of non-indexed algebras and relational systems. Coll. Math. Soc. J. Bolyai 43. Lectures in Universal Algebra, Szeged (Hungary), 1983, 365– 404.

[27] Post, E. L.: The two-valued iterative systems of mathematical logic. Ann. Math. Studies 5, Princeton Univ. Press, 1941.

[28] Rosenberg, I. G.: Über die funktionale Vollständigkeit in den mehrwertigen Logiken. Rozpravy ČSAV Řada Mat. Přirod. Věd.(Praha) 80 (1970), 3–93.

[29] Szendrei, Á.: On closed classes of quasilinear functions. Czechoslovak. Math. J. 30 (105), 498–509.

[30] Szendrei, Á.: Clones of linear operations on finite sets. Finite Algebra and Multiple-Valued Logic (Proc. Conf. Szeged, 1979), Colloq. Math. Soc. J. Bolyai 28, North-Holland, Amsterdam, 693–738.

Received September 23, 1996; revised version April 16, 1997