On Gigantic Pairs of Minimal Clones (Models of Computation and Algorithms)

(1)

On

Gigantic Pairs of Minimal Clones

fffffl

$\overline{\pi}$

(Machida,

$\mathrm{H}\mathrm{a}\mathrm{i}\mathrm{i}\mathrm{m}\mathrm{e}$

)

$*\mathrm{a}\mathrm{n}\mathrm{d}$

Ivo

G.

$\mathrm{R}\mathrm{o}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{b}\mathrm{e}\Gamma \mathrm{g}\dagger$ $*\mathrm{H}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{S}\mathrm{u}\mathrm{b}\mathrm{a}\mathrm{S}\mathrm{h}\mathrm{i}$University, \daggerUniversit\’edeMontr\’eal

1 Introduction

and Preliminary

Observations

In this paperwe deal with

some

problem fromthe ”clone theory”,which standsas araeearch areain

multiplevalued logic and universal algebra. Roughly speaking, a cloneis aset ofoperations

(func-tions) which isclosed under composition.$\uparrow 1\mathrm{A}\mathrm{s}$ an

introduction to ourproblem, onemay describe the

motivation of the problem inverysimpleand elementarywayasfollows:

$n$

Is it possible to generahize the set of operations {NOT,

OR}

on the baseset $\{0,1\}$ toa set of

operationsonthebaseset $\{0,1, \ldots,k-1\}(k\geq 2)\nabla$ ”

This iscertainly simple, but istoosimple andalmostnothing is conveyedfrom this statement. In

order to statethe problemmoreclearlyand definitely,weextract the following propertiesfromtheset

{NOT,

OR}.

(i)

_{NOT}

generatesaminimal clone$\dagger$

.

(ii)

_{OR}

generates aminimalclone.

(iii)

_{NOT,

_OR}

iscomplete\dagger ₍_$i.e.$_{, generates all the}_operations).

Ourproblemasks ifthese propertiescanbegeneralizedinto $k$-valued case.

Problem: Doesthere existapairof operations$f,g$having the above three properties(i), (\"u) and

(i\"u),in placeofNOTand OR, forarbitrary$k\geq 2$?

We shall call thisproblmSzab\’o’sproblem namedafterthefirst personwhotook upthe problem.

Now,weshallfix$k\geq 2$and set$k=\{0,1, \ldots,k-1\}$

.

Lettwo operations$f(x_{1}, \ldots,X_{m}),g(x_{1}, \ldots,x_{n})$

on$k$satispthe three properties (i), (ii) and (i\"u),that is,

(i) $[f]$ is aminimal clone.

(ii) $[g]$ isaminimalclone.

(iii) $[f,g]=O_{k}$ ($=\mathrm{t}\mathrm{h}\mathrm{e}$setof alloperationson $k$)$\dagger$

.

Here,for a set $S$of operations, $[S]^{\mathrm{f}}$ denotes theset ofall operations whichare generated by$S$

.

Moreover,we

assume

that both $f$and$g$depend

on

everyvariable, $ie$

.

$f$isanessetiallym-variable

operation and$g$isanessentiallyn–variable operation.

A pair of operations $(f,g)$ which satisfies the aboveconditions (i), (\"u) and (iii) shall be called a

gigantic pair $\mathrm{f}$

of mininaloperations.

In the following,

some

introductoryobservationsaregivenontheconditions forapair $(f,g)$ to_be

a

gigantic pair.

Claim 1

:

If$f(a, \ldots , a)=a$and$g(a, \ldots,a)=a$hold forsome$a$$\in \mathrm{k},$ $[f,g]$ isnot complete.

This is immediate from the factthat $f(a, \ldots,a)=a$and$g(a, \ldots,a)=a$ imply$h(a, \ldots,a)=a$for

anyoperation$h$whichis obtainedby compositionsof$f$and$g$

.

(2)

Clain 2 : If$m\geq 2$ and $[f]$ is aminimal clone, $f(x, \ldots,x)=x$ _forevery$x\in k$

.

(Suchoperation $f$

iscalled idempotent $\mathrm{f}.$

) Thesame istrue for$g$,ofcourse.

Thisisbecause if$f(a, \ldots,a)=b(a\neq b)$ forsome$a,b,$ $[h]\subset[f]$holdsfor unaryoperation$h$defined

by$h(x)=f(X, \ldots , x)$and $[f]$ cannot beaminimal clone.

According to Claims 1 and 2, at least one operation $f$ or $g$ must be unary operation. On the

other hand, the condition (i\"u) clearly requires that at least one operation must notbeunary. These

considerations lead tothefollowing.

Claim 3

:

Let $m\leq n$

.

Then $f$isa unaryoperation $(m=1)$ and$g$isan idempotentoperation with

2ormorevariables$(n\geq 2)$

.

The following fact characterizingaunaryoperationwhichgeneratesaminimal cloneis well-known

andeasyto$\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathfrak{h}\Gamma$

.

Claim 4

:

Supposea unaryoperation $f$ isnot the identity operation. $[f]$ isaminimal clone if and

onlyif the following (i) or (\"u) holds.

(1) $f$isnot surjective and the restrictionof$f$to Image$(f)$ is the identity operation onImage$(f)$

.

(2) $f$ isapermutationof prime order.

Aswehaveseen that$g$isanidempotent operation, $f$must beanoperationoftype (2) in Claim 4

in ordertomake the condition $(‘\dot{\mathrm{u}}\mathrm{i})$ hold. Moreover, one canassert,w.l.o.g., that

$f=(01\ldots p-1)(pp+1\ldots 2p-1)\ldots((\ell-1)p\ldots\ell p-1)$

where$k=\ell p$

.

Duetothesimilar argumentwith Claim 1wehave:

Claim 5

:

If$f(S)\subseteq S$and$g(S, \ldots,S)\subseteq S$ forsomeproper subset $S\subset k,$ $[f,g]$ is notcomplete.

Thus, when $f$isthe operationgiven above and$\ell>1,$ $g$must beanoperationwhich$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\mathfrak{g}\Gamma,$

$e.g.$, $g(\{0,1, \ldots,p-1\}, \ldots, \{0,1, \ldots,p-1\})\not\subset\{0,1, \ldots,p-1\}$

.

So far, what we have discussed is merely thevery basic properties that operations $f$and $g$must

$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{S}}\Phi$

.

Theseobservationsarethefirststepofourstudy. Byextendingthe considerationsnoredeeply,

wehave obtainedthefollowingresults whichwill be statedin detail inSection3.

(1) Weobtainedanecessary and sufficientconditionforapairofoperations $(f,g)$ to bea_gigantic

pair. (Theorem 3.1)

(2) We verifiedthat agiganticpairreallyexists forevery$k\neq 2^{t}(t>1)$by constructing such pairs.

(Theorem3.3)In ourconstruction$g$isthe joinoperator corraepondin$\mathrm{g}$to

some

semilattice $\mathrm{f}$

.

(Fig. 1)

The reader is invitedto$\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\Psi$ that thepremissin Claim

5

doesnot hold forthis operation

$g$and the

above operation $f$

.

Inthefollowing,dueto the lackof space,weshallgive only definitions andtheorems,but (almost)

noproofs.

2 Definitions

Let$\mathcal{O}_{k}^{(n)}$ be the set of alln-axyoperationsfrom $k^{n}$ into$k$andlet $o_{k}(=O_{A})= \bigcup_{n=1}^{\infty}o^{(n}k)$

.

Let$J_{k}$ be

(3)

for arbitrary $(x_{1}, \ldots,x_{n})$ in $k^{n}$

.

An operation $f\in O^{(n)}$ is idempotentif $f(x, \ldots,x)\approx x$

.

(Here and in the sequel, $\approx$ denotes an

identityover $k,$ $i.e.,$ $f(x, \ldots,x)\approx x$means $f(x, \ldots,x)=x$ for all$x\in k.$)

Deflnition 2. 1 A subset$C$

of

$O_{k}$ is $a$clone on$k$

if

(i) $C$ contains$J_{k}$ and(ii) $C$ is closed under

(functional) composition.

Definition 2. 2 Fora subset$S$

of

$\mathcal{O}_{k}$, the donegenerated by$S$ is

defined

to be the smallest done

containingS. It is denoted by $[S].$ A set $S$ iscomplete

if

$[S]=\mathcal{O}_{k}$, i.e., every operation in$\mathcal{O}_{k}$ can

be obtainedby composing operations in$S\cup J_{k}$

.

Definition 2.3 A clone $C$ on$k$ is $a$minimal clone

if

(i) $C\neq J_{k}$ and (\"u) $J_{k}\subset C’\subseteq C$ implies

$C’=C$

_for

any done$C’$ on$k$.

Definition 2. 4 An operation $f$ on$k$ is minimal

if

(i) it generates a minimal clone and (\"u) every

operation

_from

$[f]$ whose arity is smallerthanthe anty

of

$f$ is aprojection.

Theorem 2. 1 [$Ro\mathit{8}\emptyset$ Every minimal opevation belongs to one

of

thefollouring

five

types:

1) Unary operations $f$ ($1.\mathrm{e}.$, selfinaps

of

$k$) such that either (i) $f^{2}(=f\circ f)=f$ or (ii) _$f$ is a

pemutation

_of

prime order$p(1.\mathrm{e}., f^{p}=id)$

.

2)Idempotent binary opemtions; i.e., $f\in O^{(2)}$ such that$f(x,x)\approx x$.

3)Majority operations; i.e., $f\in \mathcal{O}^{\langle 3)}$ such that_{$f(x,x,y)\approx f(x,y,x)\approx f(y,x,x)\approx x$}

.

4) Semiprojections (or quasiprvjections); i.e., $f\in \mathcal{O}^{\langle n)}(3\leq n\leq k)$ such that there enists_$i(1\leq$

$i\leq n)\mathit{8}atishingf(a1, \ldots , a_{n})=a_{i}$whenever$a_{1},$$\ldots,a_{n}\in k$ are notpairurise distinct.

5)

_If

$k=2^{m}$, the temaryoperations$f(x,y, z)\approx x+y+z$ _where$<k;+>\dot{\epsilon}s$an_{$elementa\eta$}2-gmup

(1.$\mathrm{e}.$, the additive grvup

of

an_$m$-dimensionalvector space over $GF(2)$).

Definition 2. 5 A pair $(f,g)$

of

minimd operations _is _calledgigantic

if

$\{f,g\}$ is complete. $(i.e.$

,

$[f,g]=\mathcal{O}.)$

The$\dot{\mathrm{f}}\mathrm{o}$

llowing terminology isfromuniversalalgebra.

Definition 2. 6 A

$=<A;F>is$

analgebra

_if

$A$ is a set and $F$ is a set

of

finitary operations

defined

overand taking values inA. When$F=\{f_{1}, \ldots, f_{t}\}$, A is also expressed_{$as<A;f_{1},$}$\ldots,f_{t}>$

.

Foran dgebraA

$=<A;F>$

, a subset $B$

of

A $i\mathit{8}$ _$a$subuniverse

of

A

_if

$B$ is closed under

$eve\eta$

opemtion$f$ in F. A subuniverse$B$ $of<A;F>is$ $a$proper subuniverse

if

$\phi\subset B\subset A$

.

For an algebra A

$=<A;F>,$

$\theta$ is

$a$ congruence

of

A

if

$\theta$ is an equivdence relation on _$A$

and

_satisfies

the property that

_for

$eve\eta$ operation $f$ in $F$,

if

$f$ is $n- a\eta,$ $x_{1}\theta y_{1},$$\ldots,xn\theta yn$ implies

$f(x_{1,\ldots,n}X)\theta f(y_{1}, \ldots , y_{n})$

for

all$X_{1,\ldots,y_{1},\ldots,yn}X_{n},\in A.$ A congruence9

of

A $is$proper

if

$\theta$ is

not a $t\gamma\dot{\eta}\dot{m}al$equivalence relation. An algebra A _$is$simple

if

ithasnoprvpercongruences.

Moreover,

_for

an algebra A

$=<A;F>,$

$\varphi$ is anautomorphism

of

A

if

$\varphi$ is apermutation

on$A$ and

satisfies

theproperty that

for

every operation _$f$ in$F$,

if

$f$ isn-ary, $f(\varphi(x_{1}), \ldots,\varphi(X_{n}))=$

$\varphi(f(x_{1}, \ldots,x_{n}))$

for

all$x_{1},$$\ldots$,$x_{n}\in A.$ The set

of

all automorphisms

of

A is denoted by Aut A. $An$

audomorphism$\varphi$ is proper

if

$\varphi$ isnot anidentitypemutation$id_{A}$

of

$A$

.

FinaUy in this subsection,wesupplysomedefinitions conceming relations.

Definition2. 7 Foraset$A$, an$h$-ary relationon$A$isa subset

of

the Cartesianproduct$A^{h}$

.

Foran

n-aryoperation$f$ in$O_{A}$ andan$h- a\eta$relation$\rho$on$A,$ $f$is saidtopreserve$\rho$

if

$(x_{1\mathrm{j}’ j,\ldots,j}x_{2}xh)\in\rho$

for

every$j=1,2,$$\ldots,n$ implies$(f(x_{11,12}x, \ldots,X_{1n}), \ldots,f(xh1,xh2, \ldots,xhn))\in\rho$

.

Deflnition 2.8 Let$k=h^{m}$ where $h>\mathit{2}$ and$m\geq 1.$ A set$T=\{\theta_{1}, \ldots,\theta_{m}\}$

of

$e_{\Psi}4ivdence$ relations

on$k$ is an$h$-regular system

if

(i) each block(equivalence dass)

of

every$\theta_{i}$ has$h$ elements and(\"u)

if

B.

$\dot{u}$ a block

of

$\theta$

.

for

all$i=1,$$\ldots,m$ then $|B_{1}\cap\cdots\cap B_{m}|\geq 1$

.

Nezt, the relation detemined by

$T$ is the relation$\lambda_{T}$

defined

as the set

of

all$(a_{1}, \ldots,a_{h})\in k^{h}$ such that

for

each$i=1,$

$\ldots,m$ it hol&

(4)

3 Main Results

Definition 3. 1 For a$di_{\dot{\mathrm{W}}Sor}pofk$ denoteby$F_{\mathrm{p}}$the set

of

allpemutations

of

$k$ unth$\ell:=k/p$cydes

of

length$p$

.

Let$f\in F_{p}$ have cydes$C_{0},$

$\ldots,$$C_{t-1}$

.

Anequivdence relation$\theta$ on$k$ istransversal to$f$

if

there nist 1) anequivalencerelation$\lambda$

on

$\ell$

distinct

_fivm

theleast equivdence relation on$\ell$ and2) an element$c_{i}\in C_{i}$

for

each$i\in\ell$such that

$\theta=\{(f^{m}(c_{\mathrm{t}}), fm(C_{j}))|i\lambda j, 0\leq m\leq p-1\}$

.

Apemutation$\psi ofk$is orthogonal to$f$

if

1)$\psi\in F_{q}$

for

someprime$di_{\dot{\mathfrak{R}}SO}fqofk,$$2$) $f\circ\psi=\psi\circ f$

and 3)

_if

$q\neq p$ then each cyde

of

$\psi$ meets every

Ci

in at most

a

singleton.

Now,wecharacterize giganticpairs.

Theorem 3. 1 Let$f\in O^{(m)}$ and$g\in O^{\{n)}$ where_{$m\leq n$} andlet_{$\mathrm{A}:=<k;g>$}

.

Then the pair_$(f,g)$

$i\mathit{8}$gigantic

if

and only

if

(i) $m=1$ and$f\in F_{\mathrm{p}}$

for

someprime divisor$p$

of

$k$ (urith cycles$c_{0},$$\ldots,c_{\ell_{-}1}$ ),

(ii) $n>1$ and$g$ is minimd,

(i\"u) $C_{1}.\cup\cdots\cup c_{:_{h}}$ is notaprvper subuniverse

of

A

for

any$0\leq i_{1}<\cdots<i_{h}\leq\ell-1$,

(iv) Nocongruence

_of

A is tmnsversal to$f$,

(v) Noautomorphism

_of

A is orthogondto $f$,

(vi) Let$k=h^{m}$ _where$h>2$ and$m>1$

.

_If

there nist.$\cdot$ a) a pemutation

$\varphi$

of

$m$

of

order1 or$p$ and

permutations$f_{0},$$\ldots,f_{m}-1$

of

$h$ suchthat

$\alpha)f_{d_{0}}fd1\ldots fd_{\mathrm{p}-1}=id_{h}$

for

eachcyde $(d_{0}\ldots d_{\mathrm{p}-1})$

of

$\varphi$,

$\beta)$

for

every

fixed

point$i$

of

$\varphi$ the permutation$f_{i}$ is

of

orvier 1 or$p$ and

$\gamma)$

for

some

fi.

$xed$point$j$

of

$\varphi$ the permutation$f_{\mathrm{j}}$ is$fi_{Xed- p}oint- fiu$ and

of

oder$p$

and b) a bijection

$\psi:x\mapsto x=(\wedge x^{\mathrm{t}0)\ldots,\mathrm{t})},Xm-1)$

of

$k$ onto$h^{m}$ such that

for

$dlx\in k$

$\overline{f(X})=(f_{0}(x)\mathrm{t}\varphi(0)),$ $\ldots,$

$fm-1(X)\mathrm{t}\varphi(m-1)))$,

then$g$ does notpreserve the h-ary relation

{

$(a_{1},$$\ldots,a_{h})\in k^{h}|\#\{a_{1}^{\mathrm{t}},.,ai)..(p*)\}<p-1$ for every $i=0,$$\ldots,m-1$

}.

(vii) a) Let$k=p^{m},$ $\mathrm{b}$) let$x\mapsto x\wedge be$ a bijection

fiom

$k$ onto$p^{m}$ (the latter considered as theset

of

$dlm\cross 1$ matrices

over

_$p$), $\mathrm{c}$) let

for

$dlx\in k$

$\overline{f(x}\rangle=A^{\wedge}X+B$

where $A=P^{-1}JP,$ $B=P^{-1}B’$ _with $P$ a nonsingular (over $GF(p)$) $m\cross mmat\gamma\dot{\tau}x$ over_$p$,

$J$ the $m\cross mJo7danmat\dot{m}$ urith

diagon.al

_{$(1, \ldots, 1)$} and blocks

of

sizes $\ell_{1},$$\ldots,\ell_{h}$ and $B’=$

$(b_{1}, \ldots,b_{m})\in p^{m}$ is$\mathit{8}uch$ that

$(I+J+J^{2\mathrm{p}}+\cdots+J-1)B’=o_{m}\mathrm{x}1$,

and$b_{\ell_{1}+\cdots+\ell_{u}}\neq 0$

for

some

$1\leq u\leq h$

.

Then$g$ doesnotpreserve the quaternary relation $\{(_{X},y,z,t)\in k^{4}|t=x\ominus y\oplus z\wedge\}\wedge\wedge\wedge$

.

(5)

The proofof Theorem3.1heavily reliesonthefouowingtheorem.

Theorem 3.2 [Ro $70\mathrm{B}$] For a set $B$

of

surjective operations containing an essentidly

more

_than

unaryoperation, the set$Bi\mathit{8}$ complete

if

and oily

if

$(A)<k;B>is$simple andhas

no

prvpersubuniverseandnoprvper automorphism,

$(B)$

If

$k=p^{m}$

for

aprime$p$ and$m\geq 1$ and

$if<k;+>is$

an

elementaw

abelian$p$-group then some

$b\in B$ does not preservethe quaternary relation

$\{(x,y,Z,x-y+z)|x,y,z\in k\}$,

and

$(C)$

If

$k=h^{m}$ _urith _$h>2$ _and_$m>1$ _and$T$ is an $h$-regudarsystem on$k$ then some _{$b\in B$} does not

preserve$\lambda_{T}$

.

Example. Let $k=2$ (Boolean case). Thereare4nonunaryminimaloperations, namely, $\vee,$$\wedge,$ $d$and

$r$, whereV and $\wedge$ are ORand AND, $d(x,y,z)\approx$(_$x$A

$y$) ${ }$(_$y$A$z$) $\vee(z\wedge x)$ and$r(x,y, z)\approx x\oplus y\oplus z$

.

With theunarynon-identityoperation$\neg$ (NOT),twopairs $(\neg,\vee)$ and$(\neg,\wedge)$ areshowntobegigantic.

These arethe onlygiganticpairsfor $k=2$.

Next,we statethat a giganticpair reallyexistsfor every$k$whichis not apower of 2.

Theorem 3.3 For$eve\eta k$ where$k\neq 2^{t}(t>1)$, there enists agigantic pair.

Proof If$k$is

a

prime, theclaimcanbeverified for the$\mathrm{f}\mathrm{o}\mathrm{u}_{0}\mathrm{W}\mathrm{i}\mathrm{n}\mathrm{g}$twooperations: Define$f(x):\approx x$el

and$g(x,y)$ such that$g(x,y)=x$if$x=y$and $g(x,y)=k-1$ if$x\neq y$forall$x,y\in k$

.

Itiseasy to see

that$g$isminimal; in fact,$g$is a$\mathrm{s}\mathfrak{W}\mathrm{l}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{i}\mathrm{c}\mathrm{e}$join whose order is$0\leq k-1,$

$\ldots,$$k-\mathit{2}\leq k-1$

.

Supposethat $k$isacomposite number. Let

$p$denote the greatestprimedivisor of$k$and let_$\ell:=k/p$

where$\ell>1$

.

Thefollowingunaryoperation$f$ and binaryoperation$g$on $k$sufficefor ourpurpose.

Wedefine$f$bysetting

$f(ip+j):=\{$ $ip+j+1$ $i\in\ell,$ $0\leq j<p-1$,

$ip$ $i\in\ell,$ $j=p-1$

.

Thus, $f$isexpressedin thecyclicnotation as

$f=(01\cdots p-1)(pp+1\cdots 2p-1)\cdots((\ell-1)p(\ell-1)p+1\cdots k-1)$

.

An algebra$\mathrm{A}=<k;>\mathrm{i}\mathrm{s}$ asemilattice if the binaryoperator${ }$isassociative,commutativeand

idempotent ($\dot{u}e.$,it satisfies

$x(y\vee z)=(x\vee y)\vee Z,$ $x\vee y=y\vee X$ and $x\vee x=x$

for all$x,y\in k$). Thebinary relation $\leq \mathrm{o}\mathrm{n}k$corresponding to A is definedbysetting_{$a\leq b$}whenever

$a$$\vee b=b$

.

Itis well-known that $\leq \mathrm{i}\mathrm{s}$ apartial orderin which $a\vee b$is the joinof$a$and$b$

.

Conversely,

anorder $\leq \mathrm{o}\mathrm{n}k$in which eachpairhas ajoin determinesasemilattice.

Let $g$bethefollowing semilatticeoperatorV on$k$

.

Forevery$x,$ $y$in$k$set

$x\vee y=\{$

$x$ $x=y$,

$(i+1)p$ _$x=ip+j,$ $y=ip+j’$

$(0\leq i\leq$

.

$\ell-2,1\leq j,$ $j’\leq p-1,$ $j\neq j’\rangle$,

$0$ otherwise.

TheHasse diagramoftheorder corresponding to thesemilattice$<k;>\mathrm{i}\mathrm{s}$in Fig. 1. Notice that it

is

a

tree.

(6)

Figure 1: Thesemilattice for the operation V

References

[Cz 98] Cz\’edli, G., Twominimalcloneswhosejoin is gigantic,Preprint, 1998.

[Cs 83] Cs\’ak\’any, B., All ninimal cloneson athree-element set, Acta Cybemetica, 6, 1983, 227-238.

[MR 93] Machida, H. and Rosenberg, I.G., Essentially minimal groupoids, in Algebras and Otder8,

Kluwer AcademicPublishers, 1993,

287-316.

[PK 79] P\"oschel, R. and $\mathrm{K}\mathrm{a}\mathrm{l}\mathrm{u}\dot{\mathrm{z}}\dot{\mathrm{m}}\mathrm{n},$ L.A., hnktionen- und Relationenalgebren, Deutscher Verlag der

Wissenschaften, 1979.

[Qu 95] Quackenbush,R.W.,A survey ofYllinimalclones, Aequat. Math., 50, 1995, 3-16.

[Ro 65] Rosenberg, I.G.,La structuredesfonctionsde plusieursvariablessurun ensemblefini, Comptes

rendus de l’Acad. sci. Paris, 260, 1965,3817-3819.

[Ro 70A] Rosenberg, I.G.,

\"Uber

die fimktionale Voust\"andigkeit in dem mehrwertigen Logiken,

Rozpmvy $\dot{C}s$

.

Akademie $V\dot{e}d$

.

Ser. Math. Nat. Sci. Pmha, 80, 4, 1970, 3-93.

[Ro 70B] Rosenberg, I.G., Completesets for finite algebras, Math. Nachr., 44, 1970,

253-258.

$\iota \mathrm{R}_{1}86404_{-}42\mathrm{R}\mathrm{o}\mathrm{e}\mathrm{e}\mathrm{n}\mathrm{b}\mathrm{e}7.\mathrm{r}\mathrm{g},$I.G., Minimal clones I: The five types, Colloq. Math. Soc.

J. Bolyai, 43, 1986,

[Sza 92] Szab\’o, L.,Onminimal and maximalclones, Acta Cybemetica, 10, 1992,

323-327.

[Sza 97] Szatxi,L., Onninimal andmaximalclones II, Acta Cybemetica, Submitted.