Minor complexity of discrete functions

Abstract

In this paper we study a class of complexity measures, induced by a new data structure for representing k-valued functions (operations), called minor decision diagram. When assigning values to some variables in a function the resulting functions are called subfunctions, and when identifying some variables the resulting functions are called minors. The sets of essential variables in subfunctions of f are called separable in f.

We examine the maximal separable subsets of variables and their conjugates, introduced in the paper, proving that each such set has at least one conjugate. The essential arity gap gap(f) of the function f is the minimal number of essential variables in f which become fictive when identifying distinct essential variables in f. We also investigate separable sets of variables in functions with non-trivial arity gap. This allows us to solve several important algebraic, computational and combinatorial problems about the finite-valued functions.

Citation

Shtrakov, S. (2021), "Minor complexity of discrete functions", Applied Computing and Informatics, Vol. 17 No. 1, pp. 108-130. https://doi.org/10.1016/j.aci.2018.07.003

1. Introduction

The complexity of finite operations is still one of the fundamental tasks in the theory of computation and besides classical methods like substitution or degree arguments a bunch of combinatorial, and algebraic techniques have been introduced to tackle this extremely difficult problem.

A logic gate is a physical device that realizes a Boolean function. A logic circuit is a direct acyclic graph in which all vertices except input vertices carry the labels of gates. When realizing n-variable k-valued functions the circuit is called the (k,n)-circuit or Multi-Valued Logic circuit (MVL-circuit).

To move from logical circuits to MVL-circuits, researchers attempt to adapt CMOS (complementary metal oxide semiconductor), I²L (integrated injection logic) and ECL (emitter-coupled logic) technologies to implement the many-valued and fuzzy logics gates. The MVL-circuits offer more potential opportunities for the improvement of present VLSI circuit designs. For instance, MVL-circuits are well-applied in memory technology as flash memory, dynamic RAM, and in algebraic circuits [4].

In this paper we investigate a method for reduction of finite valued functions, namely by their identification minors. This method is a basic model of computing with MVL-circuits corresponding to collapsing of some inputs in the circuits. We, also study the computational complexity of this method and classify the functions in finite algebras for small values of k and n under such complexity.

Computational complexity is examined in concrete and abstract terms. The concrete analysis is based on models that capture the exchange of space for time. It is also performed via the knowledge about circuit complexity of functions. The abstract analysis is done via complexity classes, the classification of data structures, functions etc. by the time and/or space they need.

There are two key methods for reduction (computing) of the k-valued functions which are realized by assigning constants or variables to their inputs. Then the resulting objects are: subfunctions or minors, respectively. These reductions are also naturally suited to complexity measures, which illustrate “difficulty” of computing as the number of subfunctions, separable sets, and minors of the functions.

Another topic in complexity theory is to classify finite functions by their complexity such that the functions are grouped into equivalence classes with same evaluations of the corresponding complexities. Each equivalence relation in the algebra Pkn of k-valued functions determines a transformation group whose orbits are the equivalence classes (see [8,10,12]. Using the lattice of Restricted Affine Groups (RAG) in [15] we have obtained upper bounds of different combinatorial parameters of several natural equivalences in Pkn for small values of k and n. In the present paper we follow this line to study assigning (not necessarily unique) variable names to some of the input variables in a function f. This method of computing consists of equalizing the values of several inputs of f.

Section 2 introduces the basic definitions and notation of separable sets, subfunctions, minors, arity gap, etc. An important result, namely if a function has non-trivial arity gap then all its sets of essential variables are separable, complements this section. Section 3 examines the ordered decision diagrams (ODD), minor decomposition trees (MDTs) and minor decision diagrams (MDDs) of k-valued functions. In Section 3.3 we treat the minor complexities of functions with their classifications by the transformation groups. Section 4 is an illustration of the results in the paper applied to the simplest case of Boolean functions. In the Appendix we provide a classification of all ternary Boolean functions with respect to the minor complexity.

2. Subfunctions and minors of functions

A discrete function f is defined as a mapping: f:A→B where the domain A=×i=1nAi and the range B are non-empty finite or countable sets. Let X={x1,x2,…} be a countable set of variables and let Xn={x1,x2,…,xn} denote the set of the first n variables in X. Let k be a natural number with k⩾2. Let Zk denote the set Zk={0,1,…,k−1}. The operations addition “⊕” and product “.” modulo k constitute Zk as a ring. An n-ary k-valued function (operation) on Zk is a mapping f:Zkn→Zk for some natural number n, called the arity of f. Pkn denotes the set of all n-ary k-valued functions and Pk=∪n=1∞Pkn is called the algebra of k-valued logic. It is well-known fact that there are kkn functions in Pkn. For simplicity, let us assume that throughout the paper we shall consider k-valued functions, only.

For a given variable x and α∈Zk,xα is defined as follows:

xα={1ifx=α0ifx≠α.

The ring-sum expansion (RSE) of a function f is the sum modulo k of a constant and products of variables xi or xiα, (for α,α∈Zk) of f. For example, 1⊕x1x22 is a RSE of the function f in the algebra P32, with f(1,2)=2,f(2,2)=0 and f=1, otherwise. Any k instances of the same product in the RSE can be eliminated since they sum to 0. Throughout the present paper, we shall use RSE-representation of functions.

Let f∈Pkn and let var(f)={x1,…,xn} be the set of all variables, which occur in f. We say that the i-th variable xi∈var(f) is essential in f, or f essentially depends on xi, if there exist values a1,…,an,b∈Zk, such that

f(a1,…,ai−1,ai,ai+1,…,an)≠f(a1,…,ai−1,b,ai+1,…,an).

The set of all essential variables in the function f is denoted Ess(f) and ess(f)=|Ess(f)|. The variables from var(f) which are not essential in f∈Pkn are called inessential or fictive.

Let xi be an essential variable in f and let c be a constant from Zk. The function g=f(xi=c) obtained from f∈Pkn by assigning the constant c to the variable xi is called a simple subfunction of f (sometimes termed a cofactor or a restriction). When g is a simple subfunction of f we write f≻g. The transitive closure of ≻ is denoted ⪰¯. Sub(f)={g|f⪰¯g} is the set of all subfunctions of f and sub(f)=|Sub(f)|.

Let f⪰¯g, c¯=(c1,…,cm)∈Zkm and let M={x1,…,xm}⊂X with f=gm≻gm−1≻…≻g1≻g, g=g1(x1=c1), and gi=gi+1(xi+1=ci+1) for i=1,…,m−1. Then we write f⪰¯Mc¯g or equivalently, g=f(x1=c1,…,xm=cm). For brevity, sometimes we shall also use the notation f⪰¯Mg or f⪰¯g.

We say that each subfunction g of f is a reduction to f via the subfunction relationship.

Definition 2.1.

A non-empty set M of essential variables in the function f is called separable in f if there exists a subfunction g, f⪰¯g such that M=Ess(g). Sep(f) denotes the set of all the separable sets in f and sep(f)=|Sep(f)|.

The theory of separable sets (TSS) has been developed in the work of many mathematicians since the middle of the last century – K. Chimev [2], A. Salomaa [11], J. Denev, I. Gyudzhenov [7], Sl. Shtrakov [3] etc. TSS is important to avoid any redundancies when computing discrete functions and other structures as graphs [2], terms [14], etc.

Let xi and xj be two distinct essential variables in f. The function h is obtained from f∈Pkn by identifying (collapsing) the variables xi and xj, if

h(a1,…,ai−1,ai,ai+1,…,an)=f(a1,…,ai−1,aj,ai+1,…,an),

for all (a1, …, an)∈Zkn.

Briefly, when h is obtained from f, by identifying the variable xi with xj, we write h=fi←j and h is called a simple identification minor of f. Clearly, ess(fi←j)<ess(f), because xi∉Ess(fi←j), but it has to be essential in f. When h is a simple identification minor of f we write f≻h. The transitive closure of ≻ is denoted ⪰¯. Mnr(f)={h|f⪰¯h} is the set of all distinct minors of f and mnr(f)=|Mnr(f)|. Let h,f⪰¯h be an identification minor of f. The natural number r=ess(f)−ess(h),r⩾1 is called the order of the minor h of f.

We say that each minor h of f is a reduction to f via the minor relationship.

Let Mnrm(f) denote the set Mnrm(f)={g|g∈Mnr(f)&ess(g)=m} and let mnrm(f)=|Mnrm(f)|, for all m,m<n.

Let f∈Pkn be an n-ary k-valued function. The essential arity gap (shortly arity gap or gap) of f is defined as follows

gap(f)=ess(f)−maxh∈Mnr(f)ess(h).

Let 2⩽p⩽m. We let Gp,km denote the set of all k-valued functions which essentially depend on m variables whose arity gap is equal to p, i.e.

Gp,km={f∈Pkn|ess(f)=m&gap(f)=p}.

We say that the arity gap of f is non-trivial if gap(f)⩾2. It is natural to expect that the functions with “huge” gap, have to be more simple for realization by MVL-circuits and functional schemas when computing by identifying variables.

An upper bound of gap(f) for Boolean functions is found in K. Chimev [2] and A. Salomaa [11], showing that gap(f)⩽2. In [18] R. Willard also proved that if a function f:An→B depends on n variables and k<n, where k=|A| then gap(f)⩽2. It is clear that gap(f)⩽n. Thus in all cases gap(f)⩽min(n,k).

A complete description of Boolean functions with non-trivial arity gap is presented in [13]. In [16] these results are extended including the functions of k-valued logic, k⩾2. In [17], a special class of functions - namely the class of symmetric k-valued functions with non-trivial arity gap, is investigated.

Definition 2.2. Two functions g and h are called equivalent (non-distinct as mappings) (written g≡h) if g can be obtained from h by permutation of variables, introduction or deletion of inessential variables.

As mentioned earlier, there are two general ways for reduction of functions - by subfunctions or by minors. The complexities of these processes we call the subfunction or minor complexities, respectively.

An obvious difference between these concepts is the following: Each identification minor can be decomposed into subfunctions, but there are subfunctions which can not be decomposed into minors. For example, we have

fi←j=⊕m=0k−1xjm.f(xi=m,xj=m)

for all f,f∈Pkn, where f≻f(xi=m,xj=m) and f≻fi←j.

Let f=x1⊕x2⊕x3 be a Boolean function. It is easy to see that the subfunction f(x1=1)=x2⊕x3⊕1 can not be decomposed into any minors of f.

Roughly spoken, the complexity of functions, is a mapping (evaluation) Val:Pkn→N with Val(x)=c for all x∈X and for some natural number c∈N, called the initial value of the complexity, and Val(f)⩾c for all f∈Pkn.

The concept of complexity of functions is based on the “difficulties” when computing several resulting objects as subfunctions, implementations, separable sets, values, superpositions, minors, etc.

As mentioned, the computational complexities sub(f), imp(f) and sep(f) are used in [15] to classify the functions from the algebra Pkn. These complexities are invariants under the action of the suitable transformation groups.

Many computations, constructions, processes, translations, mappings and so on, can be modeled as stepwise transformations of objects known as reduction systems. Abstract Reduction Systems (ARS) play an important role in various areas such as abstract data type specification, functional programming, automated deductions, etc. [9] The concepts and properties of ARS also apply to other rewrite systems such as string rewrite systems (Thue systems), tree rewrite systems, graph grammars, etc. For more detailed facts about ARS we refer to J.W. Klop and Roel de Vrijer [9]. An ARS in Pkn is a structure W=〈Pkn,{→i}i∈I,〉, where {→i}i∈I is a family of binary relations on Pkn, called reductions or rewrite relations. For a reduction →i the transitive and reflexive closure is denoted ↠i. A function g∈Pkn is a normal form if there is no h∈Pkn such that g→ih. In all different branches of rewriting two basic concepts occur, known as termination (guaranteeing the existence of normal forms) and confluence (securing the uniqueness of normal forms).

A reduction →i has the unique normal form property (UN) if whenever t,r∈Pkn are normal forms obtained by applying the reductions →i on a function f∈Pkn then t and r are equivalent (non-distinct as mappings).

The computations on functions proposed in the present paper can be regarded as an ARS, namely: W=〈Pkn,{≻,≻}〉. Next, we show that ≻ completes the reduction process with unique normal form, whereas ≻ has not unique normal form property.

A reduction → is terminating (or strongly normalizing SN) if every reduction sequence f→f1→f2…eventually must terminate. A reduction → is weakly confluent (or has weakly Church-Rosser property WCR) if f→r and f→v imply that there is w∈Pkn such that r↠w and v↠w.

Theorem 2.3.

• (i) The reduction ≻ is UN;

• (ii) The reduction ≻ is SN, but it is not WCR.

Proof. (i) (SN) If f≻g then ess(f)>ess(g). Since the number of essential variables ess(fi) of the functions fi in any reduction sequence f≻f1≻…≻fi≻… strongly decrease, it follows that the sequence eventually must terminate, i.e. the reduction is terminating.

(WCR) Let f be a function and f≻g, and f≻h. Let t and r be normal forms such that g⪰¯t and h⪰¯r. Note that each normal form is a resulting minor obtained by collapsing all the essential variables in f. Hence, ess(t)⩽1 and ess(r)⩽1. Then we have t=f(xj,…,xj), for some xj∈Ess(f) and r=f(xi,…,xi), for some xi∈Ess(f), and hence,

t=f(xj,…,xj)≡f(xi,…,xi)=r.

Now, (i) follows from Newman’s Lemma (Theorem 1.2.1. [9]), which states that WCR & SN ⇒ UN.

(ii) Clearly, each value of a function f with ess(f)>0 is an its subfunction normal form and each subfunction of f which is not a constant is not a normal form. Hence ≻ is SN. Every non-constant functions have at least two values (normal forms), which shows that ≻ is not WCR and UN. □

Thus, for each function f(x1,…,xn) that depends on all its variables, the function f(x,…,x) is the identification minor normal form of f.

An essential variable xi in a function f∈Pkn is called a strongly essential variable in f if there is a constant ci such that Ess(f(xi=ci))=Ess(f)\{xi}. The set of all strongly essential variables in f is denoted SEss(f).

The following lemma is independently proved by K. Chimev [2] and A. Salomaa [11] in different variations.

Lemma 2.4.

[2] Let f be a function. If ess(f)>1 then f has at least two strongly essential variables, i.e. ess(f)>1⇒|SEss(f)|>1.

We are going to prove several results in TSS which will be used later to show relationship between arity gap and separable sets.

Lemma 2.5. Let N∈Sep(f). If there exist m constants c1,…,cm∈Zk such that N∩Ess(gi)=Ø where gi=f(xi=ci) for 1⩽i⩽m then M∪N∈Sep(f) for all M≠Ø,M⊆{x1,…,xm}.

Proof. It suffices to look only at the set M={x1,…,xm}. First, assume that M∩N=Ø and without loss of generality let us assume N={xm+1,…,xs},m<s⩽n. Since N∈Sep(f), there exists a vector of constants, say d¯=(ds+1,…,dn)∈Zkn−s such that N⊆Ess(g), where

g=f(xs+1=ds+1, …, xn=dn).

Let us fix an arbitrary variable from N, say the variable xs∈N. Then there exist s−m−1 constants dm+1,…,ds−1∈Zk such that xs∈Ess(h) where

h=g(xm+1=dm+1,…,xs−1=ds−1).

We have to prove that M⊆Ess(h). Let us suppose the opposite, i.e. there is a variable, say x1∈M which is inessential in h. Since x1∈{x1,…,xm}, there is a value c1∈Zk such that N∩Ess(t)=Ø where t=f(x1=c1). Our supposition shows that h=h(x1=c1) and hence, N∩Ess(h)=Ø, i.e. xs∉Ess(h), which is a contradiction. Consequently, M=Ess(h). Then g⪰¯h implies M⊆Ess(g) and hence, M∪N=Ess(g) which establishes that M∪N∈Sep(f).

Second, let M∩N≠Ø. Then we can pick P=M\N and hence, P⊆{x1,…,xm}, P∩N=Ø, and N∈Sep(f). As shown, above P∪N∈Sep(f) and M∪N∈Sep(f), as desired. □

Corollary 2.6. Let xi and xj be two distinct essential variables in f. If there is a constant c,c∈Zk such that f(xi=c) does not essentially depend on xj then {xi,xj}∈Sep(f).

Definition 2.7. Let M be an inseparable set in f. A subset M1 of M is called a maximal separable subset of M in f, if M1 is separable in f and for each M2, M1⊂≠M2⊆M it is held M2∉Sep(f).

The set of all maximal separable subsets of M in a function f is denoted by Max(M,f).

Definition 2.8. Let M1, M1∈Max(M,f) be a maximal separble subset of the inseparable set M in f. The essential variable xi in f is called an essential conjugate of the set M1 in f if for each subfunction g,f≻m2g, where M2=M\M1 we have M1∈Sep(g) and xi∈Ess(g).

Example 2.9. Let f be the following function f=x10x21⊕x20x31x42(mod 3). It is easy to see that M={x1,x3,x4}∉Sep(f) and Max(M,f)={{x1},{x3,x4}}. Clearly, x2 is an essential conjugate of both {x1} and {x3,x4} in f.

The next theorem was proven by K. Chimev, and it is an important step to achieve a series of results concerning identification minors of functions [2,3].

Theorem 2.10.

[2] Let f∈Pkn, Ø≠M∉Sep(f), M1∈Max(M, f) and M2=M\M1. Then for each subfunction g,f⪰¯M2g of f, there exists a variable xi,xi∈Ess(f)\M such that xi∈Ess(g) and M1∈Sep(g).

Note that Theorem 2.10 does not provide the existence of at least one essential conjugate of any maximal separable subset of M. We are going to strengthen Theorem 2.10 in this direction. First, we shall prove the following lemma.

Lemma 2.11. Let M be a non-empty inseparable set of essential variables in f,L=Ess(f)\M and let M1∈Max(M,f). Then there exists a subfunction g,f⪰¯Lg such that M1¬⊆Ess(g).

Proof. Without loss of generality let us assume that

M1={x1,…,xm}, M={x1,…,xm+p}and L={xm+p+1,…,xn}.

Indeed, suppose this were not the case. Then M1⊆Ess(g) for each c¯, c¯∈Zkn−m−p. Since the variable xm+1 is essential in f, there is a vector of constants b¯=(bm+p+1,…,bn)∈Zkn−m−p, such that xm+1∈Ess(t), where

t=f(xm+p+1=bm+p+1,…,xn=bn).

Let a¯=(am+2,…,am+p)∈Zkp−1 be a vector of constants from Zk such that xm+1∈Ess(v), where

v=t(xm+2=am+2,…,xm+p=am+p).

Theorem 2.10 implies M1⊆Ess(v). Clearly, Ess(v)⊆M1∪{xm+1}. Hence Ess(v)=M1∪{xm+1}, Ess(v)⊆Ess(f) and M1⊆Ess(v)⊆M with M1≠Ess(v)≠M which contradicts M1∈Max(M,f). Consequently, there is a vector c¯∈Zks of constants from Zk such that M1¬⊆Ess(g) where f⪰¯Lc¯g. □

The next theorem is a slight improvement of Theorem 2.10.

Theorem 2.12.

Let f∈Pkn,Ø≠M∉Sep(f) and let M1∈Max(M,f). Then there exists at least one essential conjugate of M1 in f.

Proof. Without loss of generality let us assume Ess(f)={x1, …, xn}, M1={x1, …, xm}and M={x1, …, xm+p}.

According to Lemma 2.11 there exists a vector c¯=(cm+p+1, …, cn)∈Zkn−p such that M1¬⊆Ess(g), where g=f(xm+p+1=cm+p+1, …, xn=cn).

Since M₁ is separable in f there exists a vector b¯=(bm+p+1, …, bn)∈Zkn−p such that M1∈Sep(h), where h=f(xm+p+1=bm+p+1, …, xn=bn).

Let s, 1⩽s⩽n−m−p be the minimal natural number for which M1∈Sept(t), where

t=f(xm+p+1=cm+p+1, …, xm+p+s−1=cm+p+s−1)

and M1∉Ess(u), where u=t(xm+p+s=cm+p+s). The number s must exist because M1¬⊆Ess(g) and M1∈Sep(h).

First, let s<n−m−p. Then M1∈Sep(t) implies that there exist constants dm+p+s, …, dn∈Zk, such that M1∈Sep(t1) and M1¬⊆Ess(t2) where

t1=t(xm+p+s=dm+p+s, …, xn=dn)

and

t2=u(xm+p+s+1=dm+p+s+1, …, xn=dn).

Pick

v=t(xm+p+s+1=dm+p+s+1, …, xn=dn).

Clearly, M1∈Sep(v) and xm+p+s∈Ess(v). If (M\M1)∩Ess(v)=Ø then we are clearly done. Next, suppose with no loss of generality that

L={x1, …, xm, xm+1, …, xm+r}⊆Ess(v)

with 1⩽r⩽p. Then L must be inseparable in v and M1∈Max(L,v). Now, Theorem 2.10 shows that xm+p+s is an essential conjugate of M₁ in v and f.

Second, let as assume s=n−m−p. Then we can pick z=f(xm+p+1=cm+p+1,…, xn−1=cn−1) with M1∈Sep(z) and M1¬⊆Ess(z(xn=cn)). The rest of the proof that xn is an essential conjugate of M1 in z and f is left to the reader. □

The improvement of Theorem 2.10 consists in the fact that we might choose the variable xi before the choice of the subfunction g,f⪰¯M2g.

A natural question to ask is there an “universal” essential conjugate xi∈Ess(f)\M for all maximal separable subsets of M, i.e. is it possible to choose the variable in Theorem 2.12 before the choice of the set M1∈Max(M, f)? The next example shows that the answer is negative.

Example 2.13.

Let k=2 and f=x1x4x50⊕x2x40x6⊕x3x5x60. Clearly M={x1, x2, x3}∉Sep(f) and Max(M, f)={{x1}, {x2}, {x3}}. Also, it is easy to verify that x6∉Ess(f(x2=0, x3=0)), x5∉Ess(f(x1=0, x3=0))and x4∉Ess(f(x1=0, x2=0)). The essential conjugates of the maximal separable subsets are: {x4, x5} of {x1},{x4,x6} of {x2}, and {x5, x6} of {x3}.

Let us turn our attention to the following:

• 1. Each simple minor obtained by collapsing pairs of variables belonging to distinct maximal separable subsets of M depends on possible maximal number of essential variables. Thus we have ess(f2←1)=ess(f3←1)=ess(f3←2)=5. For instance, f2←1=x1x4x50⊕x1x40x6⊕x3x5x60.

• 2. The simple minors obtained by pairs of essential conjugates essentially depend on four variables, for instance, f5←4=x2x40x6⊕x3x5x60.

Next, we turn our attention to relationship between essential arity gap and separable sets in functions.

Theorem 2.14.

Let f∈pkn. If gap(f)⩾2 then each non-empty set of essential variables is separable in f.

Proof. Let M be an arbitrary non-empty set of essential variables in f. We prove that M∈sep(f) by considering cases. The theorem is given to be true if n⩽2. Next we assume n>2.

Case 1: gap(f)=2, n⩾3 and k=2.

If n=3 then Theorem 3.2 [13] implies that f=x3α(x10x21⊕x11x20)⊕x1βx2β or f=x3α(x10x20⊕x11x21)⊕x3¬(α)(x10x21⊕x11x20), where α, β∈{0, 1}. Clearly, each set of essential variables in f is separable.

If n=4 then according to Theorem 3.3 [13] we have f=x40.g(x1, x2, x3)⊕x41.h(x1, x2, x3), with g=x3α(x10x20⊕x11x21)⊕x3¬(α)(x10x21⊕x11x20), and h=x3¬(α)(x10x20⊕x11x21)⊕x3α(x10x21⊕x11x20), for some α, α∈{0, 1} (here ¬(α) means negation of α). Clearly, each set of essential variables in f is separable.

Let n⩾5 From Theorem 3.4 in [13] it follows that

f=⊕α1⊕⋯⊕αn=1x1α1⋯xnαnor f=⊕α1⊕⋯⊕αn=0x1α1⋯xnαn.

Thus we have Ess(f)=Xn. Suppose, with no loss of generality that M={x1,⋯,xm},m<n and

f=⊕α1⊕⋯⊕αn=1x1α1⋯xnαn.

Let c1,⋯,cn∈Zk and c1⊕⋯⊕cn=1. We can pick g=f(xm+1=cm+1,⋯,xn=cn) and r=cm+1⊕⋯⊕cn. Assume without loss of generality that r=1. Then we have

g=⊕α1⊕⋯⊕αn=1x1α1⋯xmαm.

It must be shown that M=Ess(g). By symmetry, it is enough to show that x1∈Ess(g). Let c2,⋯,cm∈Zk with c2⊕⋯⊕cm=0. Then we have

g(0,c2,⋯,cm)=1 and g(1,c2,⋯,cm)=0,

which proves that x1∈Ess(g).

Case 2: gap(f)=2,2<k<n.

Theorem 2.1 [18] implies that f is a symetric function which essentially depends on all of its n variables. Theorem 4.1 [17] states that: If f is a symmetric function with non-trivial arity gap, then each set of essential variables in f is separable, which completes the proof of this case.

Case 3: gap(f)=2,n=3 and k⩾3.

Lemma 5.1 [16] states that if f∈G2,k3 then ess(fi←j)=1 for all i,j∈{1,2,3},i≠j, which shows that each subset of X3 is separable in f.

Case 4: gap(f)=2,4⩽n⩽k.

If f is a symmetric function then we are done because of Theorem 4.1 [17] and if f is not a symmetric function then according to Theorem 4.2 [16] there exist n−2 variables yl1,⋯,yln−2∈Xn such that f=h⊕g,where Ess(h)={yl1,⋯,yln−2} and g∈Gn,kn. Moreover gi←j=0 for all 1⩽i,j⩽n with i≠j. Now, the proof can be done as in Case 6:, for p=2, given below.

Case 5: gap(f)=n,3⩽n⩽k.

From Theorem 3.1 [16] it follows that f is presented in the following form:

(1)f=a0[⊕α∈Eqknxα]⊕[⊕β∈Disknarxβ]

where Eqks={γ∈Zks|∃i,j,1⩽i<j⩽s,γi=γj}, γ=γ1⋯γs,xγ=x1γ1x2γ2⋯xsγs and Disks=Zks\Eqks, for s,s⩾2. Moreover, there exist at least two distinct numbers among ar∈Zk for r=0,1,⋯,kn−1.

It is easy to see that Ess(f)=Xn. We have to show that M∈Sep(f). Without loss of generality let us assume that M={x1,⋯,xm},1⩽m⩽n. If m=n or m=1 we are clearly done. Let 1<m<n and let r=∑i=1nβikn−i be a natural number such that ar≠0. Then we have g=f(xm+1=βm+1,⋯,xn=βn)=a0[⊕δ∈Eqkmxδ]⊕[⊕σ∈Diskmajxσ],

where j=∑i=1nσikn−i with σi=βi for i=m+1,⋯,n, and there are at least two distinct numbers among aj. Clearly, g essentially depends on all of its variables, i.e. Ess(g)=M and hence M∈Sep(f).

Case 6 gap(f)=p,2⩽p<n, and 4⩽n<k.

According to Theorem 3.4 [16], there exist functions h and g, such that f=h⊕g, where g∈Gn,kn and ess(h)=n−p. Without loss of generality, let us assume that Ess(h)={x1,⋯,xn−p}. Moreover, gi←j=0 for all i and j,1⩽j<i⩽n.

Clearly, Ess(f)=Xn and according to Theorem 3.1 [16] and the Eq. (1), given in Case 5, the function g can be represented as follows g=u⊕v, where

(2)u=[⊕β∈Disknarxβ]and v=a0[⊕α∈Eqknxα].

Let xi,xj∈Xn, i>j, be two arbitrary essential variables in g. Say i=n and j=n−1, for simplicity. Then we have

(3)ui←j=0 and  vi←j=a0[⊕δ∈zkn−2x^δ]=a0.

Since gi←j=0 for all i and j, 1⩽j<i⩽n we have vi←j=a0=0 and hence v=0, and g=u. Let M be a set of essential variables in f. Note that M∈sep(g), according to Case 5 and if M∩Ess(h)=Ø then M∈sep(f).

We have to prove that M is separable in f in each other case. We argue by induction on n-the number of essential variables in f and g.

Let n = 4. This is our basis of induction.

First, let |M|=2 and P=2. Clearly, if M⊆Ess(h) then (2) and (3) show that M∈Sep(f). Next, let us assume that M={x1, x3} and Ess(h)={x1, x2}. Let c2,c4∈Zk be two constants, such that Ess(t1)={x1, x3}, where t1=g(x2=c2,x4=c4). Clearly, x3∈Ess(f1), where f1=f(x2=c2,x4=c4). Let h1=h(x2=c2). If x1∉Ess(h1) then x1∈Ess(f1) and obviously, M∈sep(f). If x1∈Ess(h1) then f1=h1(x1)⊕t1(x1,x3). According to (2) and (3) there is a constant c3=Zk, such that Ess(t1(x3=c3))=Ø. Hence x1∈Ess(f1(x3=c3)) and M∈sep(f), again.

Second, let |M|=3 and P=2, and Ess(h)={x1, x2}.

Let x1∉M. Then there is a constant c1∈Zk such that x2∈Ess(h2), where h2=h(x1=c1). Thus, (2) implies that {x2, x3,x4}=Ess(f2), where f2=f(x2=c1) and M∈sep(f), again.

Let x4∉M. Then there is a constant d4∈Zk such that x3∈Ess(t2), where t2=g(x4=d4). Clearly, x3∈Ess(f3), where f3=f(x4=d4). According to (2) and (3), we have f3=(x3=d4)=h(x1,x2)⊕a0, which shows that {x1, x2,x3}=Ess(f3) and hence M∈sep(f).

One can argue similarly if P=3 and n=4.

Let us assume that for some natural number l,l⩾4, if n<l,2⩽p,l<k and f∈Gp,kn, then each set of essential variables in f is separable.

Let us pick n=l. According to Lemma 2.4 there is a strongly essential variable x_i, 1⩽i⩽l in g, and let ci∈Zk be a constant such that Xl\{xi}=Ess(g(xi=ci)). Without loss of generality, let us assume that i=l and ci=k−1. Using (2), it is easy to verify that

(4)t3=g(xl=k−1)=[⊕β∈Disk−1l−1brx˜β],

where the coefficients br linearly depend on a0, …, akl−1 and x˜β=x1β1…xl−1βl−1.

By p⩾2 it follows that we may reorder the variables in h such that Ess(h)={x1,…xl−p} with l−p<l−1.

Then we can pick f4=f(xl=k−1)=h⊕t3. It must be shown that Ess(f4)=Xl−1. Since p⩾2 it follows that N=Ess(f4)\Ess(h)≠Ø. Next, using (2) one can show that N∈Sep(t3) and N∈Sep(f4). According to (3) we have

N∩Ess(f4(xi=k−1))−Ø,

for all i=1, …, l−p. Now, Lemma 2.5 implies N∪{x1,…,xl−p}∈Sep(f4). Hence Ess(f4)=xl−1. According to (4) it follows that f4∈Gp,k−1l−1.

Therefore the inductive assumption may be applied to f4, yielding M∈Sep(f4), and hence M∈sep(f). □

3. Decision diagrams of functions

3.1 Ordered decision diagrams

Intuitively, it seems that a function f has the maximal complexity under the subfunction reduction if all its sets of essential variables are separable, because the variables from separable sets remain essential after assigning constants to other variables (see [15]). For example, when assigning Boolean constants to some variables of a Boolean function, then a natural complexity measure is the size of its Binary Decision Diagrams (BDDs), which also depend on the variable ordering (see [1]). Each path from the root (function node) to a terminal node (leaf) of BDD is called an implementation of f. The subfunction complexities imp(f),sub(f) and sep(f) of all implementations, subfunctions, and separable sets, obtained under all n! variable orderings of n-ary Boolean functions for n,n⩽5, are studied and calculated in [15].

Example 3.1.

Let f=x1x40⊕x10x3⊕x2x3⊕x2x4(mod 2) and g=x1⊕x2⊕x3⊕x4(mod 2) be two Boolean functions. Figure 1 presents their BDDs under the natural variable ordering x1;x2;x3;x4. All sets of essential variables in g are separable, whereas the sets (x1,x2) and (x3,x4) are inseparable in f. Clearly, f has non-trivial essential arity gap and f∈G2,24. Note that the implementations (longest paths) in Figure 1 A) consist of three edges, but in Figure 1 B) of four edges, which shows that the BDD of the function g is extremely complex with respect to the number of its subfunctions and separable sets, whereas the BDD of f is simpler.

3.2 Minor decision diagrams

Next we introduce a new graph-based presentation of the k-valued functions, namely by the minor decision diagrams.

The minor decomposition tree (MDT) of a function, consists of the node, labelled f – called the function node and nodes labelled with minor names, called the internal (non-terminal) nodes, and the rectangular nodes (leaves of the tree) called the terminal nodes. The terminal nodes are labelled with the same name of a function (atomic minor) from Pk1 (according to Theorem 2.3). The terminal and non-terminal nodes in the MDT for a function f, essentially depending on n variables, are disposed into maximum n−1 layers of the tree. The i-th layer consists of names of all the distinct minors of order i, for i=1,…, n−1. Figure 2 presents the MDT of the function f=x1x40⊕x10x3⊕x2x3⊕x2x4, given in Example 3.1.

We introduce the minor decision diagrams (MDDs) for k-valued functions constructed by reducing their minor decomposition trees (MDTs). Let f be a k-valued function. The minor decision diagram (MDD) of f is obtained from the corresponding MDT by reductions of its nodes and edges applying of the following rules, starting from the MDT and continuing until neither rule can be applied:

Reduction rules

• If two edges have equivalent (as mappings) labels of their nodes they are merged.

• If two nodes have equivalent labels, they are merged.

Example 3.2.

Let us build the MDDs of the functions from Example 3.1, namely f=x1x40⊕x10x3⊕x2x3⊕x2x4(mod 2) and g=x1⊕x2⊕x3⊕x4(mod 2) using the reduction rules and their MDT’s.

Figure 3 A) shows the MDD of the function f, and Figure 3 B) presents the MDD of g. The identification minors of f and g are:

f2←1=f4←3=x1⊕x3,f2←1≡f4←3≡[f3←1]4←2≡[f4←2]2←1f4←2=x1x20⊕x10x3⊕x2x30.gi←j≡g2←1=x3⊕x4,[g2←1]4←3=0.

f3←1=x1x40⊕x1x2⊕x2x4,f3←1≡f4←1≡f3←2for 1≤j<i≤4 and,

Each edge e=(v1, v2) in the diagram is supplied with a label l(v1, v2), (written as bold in Figure 3A), which presents the number of the merged edges of the MDT, connecting the nodes v1 and v2 in MDT.

If two nodes in MDT are connected with unique edge then this edge is presented in MDD without label, for brevity. For example, such pairs are (f,f4←2),(f3←1, f2←1) and (f2←1, 0).

The label of the edge (f, f3←1) is 3 because there are three identification minors, namely f3←1, f4←1 and f3←2 of f which are equivalent to f3←1 (see Figure 2).

In a similar way we count the labels of the edges in Figure 3 B).

So, the MDD of f is an acyclic directed graph, with unique function node and according to Theorem 2.3, with unique terminal node. Clearly, the MDD and MDT are uniquely determined by the function f.

3.3 Complexity and equivalence relations with respect to minor reduction

Many of the problems in the applications of the k-valued logic are compounded because of the large number of the functions, namely kkn. Techniques which involve enumeration of functions can only be used if k and n are trivially small. A common way for extending the scope of such enumerative methods is to classify the functions into equivalence classes by some natural equivalence relation.

Let SA denote the symmetric group of all permutations of the non-empty set A, and let Sm denote the group S{1.,…,m} for a natural number m, m⩾1.

A transformation ψ:Pkn→Pkn is an n-tuple of k-valued functions ψ=(g1,…,gn), g1∈Pkn,i=1,…,n, acting on a function f=f(x1…xn)∈Pkn as follows ψ(f)=f(g1,…,gn). Then the composition of two transformations ψ   and φ=(h1…hn) is defined as follows

ψφ=(h1(g1…gn),…,hn(g1…gn)).

The set of all transformations of Pkn is the universal monoid Ωkn with unity - the identical transformation ϵ=(x1…xn). When taking only invertible transformations we obtain the universal group Ckn which is isomorphic to the symmetric group Szkn. The groups consisting of invertible transformations of Pkn are called transformation groups (sometimes termed permutation groups).

Let ≃, ≃⊆Pkn×Pkn be an equivalence relation on the algebra Pkn. Since Pkn is a finite algebra of k-valued functions, the equivalence relation ≃ makes a partition of the algebra in a finite number equivalence classes.

A mapping ϕ:Pkn→Pkn is called a transformation preserving ≃ if f≃ϕ(f) for all f∈Pkn. Taking only invertible transformations which preserve ≃, we get the group G≃ of all transformations preserving ≃. The orbits (also called G≃-types) of this group are denoted by P1, …, Pr.

Our aim is to classify functions from Pkn into equivalence classes by ≃. Thus we have to calculate the number r of G≃-types, to count the number of functions in different equivalence classes, i.e. compute the cardinalities of the sets P1, …, Pr and to create a list of functions belonging to different G≃-types.

Let f∈Pkn and let nof(f) denote the normal form obtained by applying the reduction ≻ on f. According to Theorem 2.3, the normal form nof(f) is unique and nof(f)∈Pk1. Thus, our first natural equivalence is defined as follows:

Definition 3.3.

Let f and g be two functions from Pkn. We say that f and g are nof-equivalent (written f≃nofg) if nof(f)=nof(g).

The transformation group induced by nof-equivalence is denoted NFkn. The transformations in NFkn preserve ≃nof, i.e. nof(g)=nof(ψ(g)) for all g∈Pkn and ψ∈NFkn. Since the atomic minors (labels of terminal nodes in MDD) depend on at most one essential variable, it follows that the number of the orbits of NFkn is equal to |Pk1|=kk. These transformations involve permuting variables, only (see Theorem 3.9, below).

By analogy with the ordered decision diagrams [1,15], we define several equivalence relations in Pkn, which allow us to classify the functions by the complexity of their MDDs.

The “scalability” of the diagram is an important measure of the computational complexity of the function. We are going to formalize this problem and establish a method for classification of functions by the minor complexities.

First, the number mnr(f) of all the minors of a function f is a complexity measure, which can be used to evaluate the MDD of f. Namely, it counts the size (number of terminal and non-terminal nodes) of the MDD. M. Couceiro, E. Lehtonen and T. Waldhauser have studied similar evaluation, named “parametrized arity gap” in [5,6], which characterizes the sequential identification minors of a function.

Second, we are going to classify functions in finite algebras under the complexity measures which count the number of minors and the number of ways to obtain these minors.

Definition 3.4.

Let f∈Pkn be a k-valued function. Its cmr-complexity cmr(f) is defined as follows:

• (i)cmr(f)=1 if ess(f)⩽1;

• (ii)cmr(f)=2 if ess(f)=2;

• (iii)cmr(f)=∑j<i,xi,xj∈Ess(f)cmr(fi←j) if ess(f)⩾3.

The minors fi←j with i<j are excluded because fi←j≡fj←i. The minor complexity cmr can be inductively calculated using the MDDs of the functions as it is shown in Example 3.5, given below. We start to assign cmr-complexity equals to 1 for the terminal node, which is labeled by the minor of “0” of highest order according to (i) of Definition 3.4. Next, we inductively calculate the cmr-complexity of the minors of f with lower order, applying (ii) and (iii) of Definition 3.4.

Example 3.5.

Let us count the cmr-complexity of the function f from Example 3.1 , using the identification minors of f obtained in Example 3.2 and MDD of f, given in Figure 3 A). There is two simple minors (f2←1and f4←3) of order 2 and four simple minors of order 1. Thus we have cmr(f2←1)=cmr(f4←3)=2, cmr(f3←1)=cmr(f4←1)=cmr(f3←2)=1∗2+2∗1=4 and cmr(f4←2)=3∗2=6. According to Definition 3.4 we have cmr(f)=2∗2+1∗6+3∗4=22.

In a similar way from the MDD of g in Figure 3 B) we obtain cmr(g)=6∗2=12.

Definition 3.6.

Let f and g be two functions with ess(f)=n, n⩾0. We say that f and g are cmr-equivalent (written f≃cmrg) iff:

• (i) n⩽1⇒ess(f)=ess(g);

• (ii) n⩾2⇒ there exists a bijection σ:Ess(f)→Ess(g), such that fi←j≃cmrgr←s, where xr=σ(xi)and xs=σ(xj), for all j, i, with xi,xj∈Ess(f), j<i.

Let CMkn denote the transformation group preserving the equivalence ≃cmr, i.e. ψ∈CMkn if and only if ψ(f)=g⇒f≃cmrg.

The nof-equivalence is independent on the cmr-complexity of functions, defined by reduction via minors. For example, the functions f=0 and g=x10x2⊕x1x2x30(mod 2) are nof-equivalent, but they are not cmr-equivalent.

Next we define another equivalence based on the number of minors (size of MDD) in a function.

Definition 3.7. Let f and g be two functions from Pkn. We say that f and g are mnr-equivalent (written f≃mnrg) if mnrm(f)=mnrm(g) for all m, 0⩽m⩽ess(f)−1.

Clearly, if ess(f)⩽1 then Mnr(f)=Ø. Hence, if ess(f)=ess(g)⩽1 then f≃mnrg. MNkn denotes the transformation group which preserves the equivalence ≃mnr.

Note that f≃mnrg or f≃nofg do not imply ess(f)=ess(g), which can be seen by the following functions: f=x10x21(mod 3) and g=x10x21x32(mod 3). Clearly, f≃mnrg and f≃nofg, but ess(f)=2, and ess(g)=3.

Theorem 3.8.

• (i)f≃cmrg⇒cmr(f)=cmr(g);

• (ii) f≃cmrg⇒f≃mnrg.

Proof. We argue by induction on the number n=ess(f).

If ess(f)⩽2 (basis for induction) then we are clearly done. Assume that (i) and (ii) are satisfied when n<s for some natural number s, s>2. Let n=s and f≃cmrg. Then our inductive assumption implies

cmr(f)=∑j<icmr(fi←j)=∑u<vcmr(gu←v)=cmr(g),

and mnrm(fi←j)=mnrm(gu←v), where u=π(i) and v=π(j) for some π∈Sn and m=0, …, n−1. □

Thus, the complexity cmr(f) is an invariant of the group CMkn, and the complexity mnr(f) is an invariant of the group MNkn.

It is naturally to ask which groups among “traditional” transformation groups are subgroups of the groups NFkn or CMkn and which of these groups include NFkn, MNkn or CMkn as their subgroups.

Let σ:Zk→Zk be a mapping and let ψσ:Pkn→Pkn be a transformation of Pkn generated by σ as follows ψσ(f)(a¯)=σ(f(a¯)) for all a¯∈Zkn.

Theorem 3.9.

The transformation ψσ preserves ≃cmr if and only if σ is a permutation of Zk, k>2.

Proof. Let σ:Zk→Zk.

First, let σ be a permutation of Zk. Let f∈Pkn be an arbitrary function. If ess(f)⩽1 then ess(ψσ(f))=ess(f) and we are clearly done. Let ess(f)=ess(g)=n⩾2 and let i and j be two arbitrary natural numbers with 1⩽j<i⩽n. Then we have

[ψσ(f)]i←j(x1, …, xn)=σ(fi←j(x1, …, xn)).

Since σ is a permutation, it follows that fi←j≃cmr[ψσ(f)]i←j which shows that f≃cmrψσ(f).

Second, let σ be not a permutation of Zk. Hence, there exist two constants a1 and a2 from Zk such that a1≠a2 and σ(a1)=σ(a2). Let b¯=(b1, …, bn)∈Zkn, n⩾2 be a vector of constants from Zk. Then we define the following function from Pkn:

f(x1,…,xn)={a1 if xi=bi  for  i=1,…,na2otherwise.

Clearly, Ess(f)=Xn and the range of f consists of two numbers a1 and a2. Then σ({a1, a2})={σ(a1)}, implies that ψσ(f)(c1, …, cn)=σ(a1) for all (c1, …, cn)∈Zkn. Hence, Ess(ψσ(f))=Ø which shows that f¬≃cmrψσ(f) and ψσ∉CMkn.□

We deal with “natural” equivalence relations which involve variables of functions. Such relations induce permutations of the domain Zkn of the functions. These mappings form a transformation group whose number of equivalence classes can be determined. The restricted affine group (RAG) is defined as a subgroup of the symmetric group on the direct sum of the module Zkn of arguments of functions and the ring Zk of their outputs. The group RAG permutes the direct sum Zkn+Zk under restrictions which preserve single-valuedness of all functions from Pkn [8,10].

In the model of RAG an affine transformation ψ operates on the domain or space of inputs x=(x1, …, xn) to produce the output y=xA⊕c, which might be used as an input in the function f. Its output f(y) together with the function variables x1, …, xn are linearly combined by a range transformation which defines the image g=ψ(f) of f as follows:

(5)g(x)=ψ(f)(x)=f(y)⊕a1x1⊕…⊕anxn⊕d=f(xA⊕c)⊕atx⊕d,

where d and ai for i=1, …, n are constants from Zk, c∈Zkn, and a=(a1, …, an)∈Zkn. Such a transformation belongs to RAG if A is a non-singular matrix.

We want to extract basic facts for several subgroups of RAG which are “neighbourhoods” or “relatives” of our transformation groups NFkn, CMkn and  MNkn.

First, a classification occurs when permuting arguments of functions. If π∈Sn then π acts on variables by: π(x1,⋯,xn)=(xπ(1),⋯,xπ(n)). Each permutation generates a map on the domain Zkn.

For example, the permutation π=(1,2,3) generates a permutation of the domain {0,1,2}3 of the functions from P33. Then we have π:001→010→100 and in cyclic decimal notation this permutation can be written as (1,3,9). The remaining elements of Z33 are mapped according to the following cycles of π in decimal notation - (2,6,18)(4,12,10) (5,15,19)(7,21,11)(8,24,20) (14,16,22)(17,25,23). Note that each permutation from Sn keeps fixed all k constant tuples from Zkn. In case of Z33, these tuples (0,0,0),(1,1,1) and (2,2,2) are presented by the decimal numbers 0,13 and 26.

Skn denotes the transformation group induced by permuting of variables. Boolean functions of two variables are classified into twelve S22-classes [8], as it is shown in Table 1. M. Harrison has determined the cycle index of the group S2n. Using Polya’s counting theorem he has counted the number of equivalence classes under permuting arguments (see [8] and Table 3, below).

The subgroups of RAG, defined according to (5) which are “relatives” to the groups NFkn,CMkn and MNkn are determined as follows: RAG when A-non-singular; CFkn when A=I,a=0,c=0; LFkn when A=I,c=0,d=0; CAkn when A=I,a=0,d=0; LGkn c=0,a=0,d=0; Skn when A=P,c=0,a=0,d=0, where P denotes a permutation matrix, I is the identity matrix, bandc are n-dimensional vectors from Zkn and d∈Zk.

It is naturally to ask which subgroups of RAG are subgroups of NFkn,CMkn and MNkn. Theorem 3.8 shows that CFkn and Skn are subgroups of MNkn. Clearly, Skn⩽NFkn.

Theorem 3.10.

Proof. (i) Follows from Theorem 3.9.(ii) and (iii) – Let π∈Sn and let φπ:Pkn→Pkn be a transformation of Pkn defined as follows φπ(f)(a1,⋯,an)=f(aπ(1),⋯,aπ(n)) for all (a1,⋯,an)∈Zkn. We have to prove that the transformation φπ preserves the equivalence relations ≃cmr,≃mnr and ≃nof for all π∈Sn. It suffices to show that φπ preserves ≃cmr and ≃nof. Let f∈Pkn be a function and let us assume Ess(f)=Xn,n⩾2. It must be shown that f≃cmrg and f≃nofg, where g(a1,⋯,an)=f(π(a1),⋯,π(an)) for all (a1,⋯,an)∈Zkn. Since π is a permutation, we have

f(a1,⋯,an)=g(π−1(a1),⋯,π−1(an)),

for all (a1,⋯,an)∈Zkn which shows that f≃cmrg and hence, f≃cmrφπ(f). Since nof(f)=f(xi,⋯,xj) and nof(f)=f(xπ(i),⋯,xπ(i)), it follows nof(g)≡nof(g) and f≃nofg.(iv) and (v) – Let f=x1⊕x2⊕x3(mod 3) and g=x1x2⊕x1x3⊕x2x3(mod 3). Then we have fi←j=2xj⊕xm(mod 3) and gi←j=2xjxm⊕xjxj(mod 3) where {i,j,m}={1,2,3}. Clearly, fi←jj←m=gi←jj←m=0, and hence f≃cmrg and f≃nofg. One can show that there is no transformation ψ∈RAG, defined as in (5), for which g=ψ(f). Consequently, CMkn¬⩽RAG,NFkn¬⩽RAG and MNkn¬⩽RAG.(vi), (vii), (viii), (ix) and (xi) – Let f=x10x21⊕x20x31x42(mod 3) and g=x01x21⊕x20x31x41(mod 3) be the functions from P34. Let

A=(1000010000100002)

Then clearly, f(x)=g(Ax) and hence, f and g belong to the same equivalence class under the transformation group LG34. Let c=(0,0,0,1). Then we have f(x)=g(x.I⊕c), which shows that f and g belong to the same equivalence class under the transformation group CA34. One can show that f≃nofg. Example 3.5 shows that f¬≃mnrg. Consequently, NFkn¬⩽MNkn,LGkn¬⩽MNkn and CAkn¬⩽MNkn. Theorem 3.8 shows that NFkn¬⩽CMkn,LGkn¬⩽CMkn and CAkn¬⩽CMkn.(x) - Let us pick f=x10x20(mod 2) and g=x1x2(mod 2). Clearly, f≃cmrg, but nof(f)=x10¬≡x1=nof(g).□

So, Theorem 3.10 summarizes results which determine the positions of the groups NFkn,CMkn and MNkn, with respect to the subgroups of RAG. It is well-illustrated by Figure 4, in the case of Boolean functions.

4. Classification of Boolean functions by minor complexities

Table 2 shows the four classes in P22 under the equivalence ≃cmr. The ≃cmr-classes are represented as union of several classes under the permuting arguments, according to Theorem 3.10 (ii), which can be observed in Table 1 and Table 2, given below.

The number of types under permuting arguments, is an upper bound of the number of equivalence classes induced by the relations ≃nof,≃cmr and ≃mnr (see Figure 4).

In Table 3 the columns named SB2n and SP2n are calculated in [15] and they present the number of classes under the complexities, determined by the number of subfunctions and separable sets in the functions. It is surprising that for n⩽3 these columns are same as the columns CM2n and MN2n, i.e. the number of classes are the same, but these classes are very different as sets of functions, determined by these complexities.

Figure 4 presents the subgroups of RAG and transformation groups whose invariants are subfunction, and minor complexities of Boolean functions of n-variables. According to Theorem 3.10 the group CM2n has three subgroups from RAG, namely: S2n - the group of permuting arguments, trivial group consisting of the identity map, and CF2n- the group of complementing outputs. The groups NF2n and MN2n are not subgroups of any subgroup of RAG.

Next, we turn our attention on classifying the functions with respect to their cmr-complexity. This classification is based on the exhaustive Algorithm 1, given below.

Table 4 presents a complete classification of the Boolean functions of tree variables by the minor complexities cmr and mnr. If we agree to regard each 2³-tuple as a binary number then the last column presents the vectors of values of all ternary Boolean functions in their table representation with the natural numbers from the set {0,⋯,127}. According to Theorem 3.9, if a natural number z,0⩽z⩽255, presents a function f which belongs to a cmr-class then the function f^ presented by 255−z belongs to the same class. Thus the catalogue contents the numbers ⩽127, only (see the last column in Table 4). These numbers represent the functions which preserve zero, i.e. the functions f for which f(0,0,0)=0. This classification shows that there are eleven equivalence classes under ≃cmr and five classes under ≃mnr.

Theorem 3.8 shows that each mnr-class is a disjoint union of several cmr-classes. Thus the first mnr-class consists of all the functions which belong to the first and the second cmr-class (see fifth column in Table 4). The second mnr-class is equal to the third cmr-class. The fourth and the fifth mnr-classes are unions of three cmr-class, namely: sixth, seventh, and eight, and ninth, tenth, and eleventh, respectively.

The main data structure which describes the nodes in the MDD of f is represented by a record declared as follows:

The first field, named ess presents the number of essential variables in the minor (located on the corresponding node) and the second field val is a natural number whose k-ary representation is the last column B of the truth table (of size kn×(n+1)) of the minor.

Table 4 presents classification of ternary Boolean functions under the equivalences ≃cmr and ≃mnr, including the catalogue of the equivalence classes (last column). Let us choose a natural number belonging to the seventh column of Table 4, say 24. It belongs to the row numbered 6. The binary representation of 24 is 00011000, because 24=1∗24+1∗23. Hence, the function f corresponding to 24 is evaluated by 1 on the fourth and fifth miniterms, namely x10x2x3 and x1x20x30. Consequently, f=x10x2x3⊕x1x20x30(mod 2). Then we have f2←1=f3←1=0 and f3←2=x10x2⊕x1x20(mod 2). Clearly, cmr(f)=4, which is written in the third cell of the sixth row. The MDD of f is shown in the second cell. The cmr-equivalence class containing f consists of 18 functions, according to the fourth cell of the sixth row and the mnr-equivalence class of f contains 108 functions (see whole fifth column of the table). The function x1x2x30(mod 2) is representative for this class (sixth cell). The numerical list of the functions from this equivalence class is given in the last seventh cell of Table 4. The record of the function f is presented as follows f.ess=3 and f.val=24, where k = 2 and B= 00011000.

5. Conclusion

The transformation groups whose invariants are the minor complexities have only three subgroups among the groups in RAG, namely trivial group (identity map), Skn and CFkn, whereas the groups whose invariants are the subfunction complexities have three subgroups more (see [15]). One of motivations to study the group NFkn is that the reductions are inexpensive and the number of classes is much smaller than the number of classes under the subgroups of RAG, because the order of NFkn is so large. As mentioned, the number of equivalence classes under NFkn equals to kk. Hence, the order of NFkn is equal to kkn/kk=kkn−1.

The most complex functions with respect to separable sets [15] are grouped in the largest equivalence class. J. Denev and I. Gyudzhenov in [7] proved that for almost all the k-valued functions all the sets of essential variables are separable. Similar results can not be proved for the minor complexities. For example, in P23 the most complex functions belong to the class numbered as 11 (see Table 4), which consists of 16 functions. This class is not so large. It presents 1/16 of the all 256 ternary Boolean functions.

Figures

Figure 1

Binary Desicion Diagrams.

Figure 2

MDT of f=x1x40⊕x10x3⊕x2x3⊕x2x4(mod 2).

Figure 3

Minor decision diagrams.

Figure 4

Transformation groups in P2n.

Table 1

The twelve classes in P22 under the permutating of variables.

[0],	[x10x20],	[x10x2, x1x20],	[x1, x2],
[x1⊕x2],	[x1⊕x20],	[x10⊕x1x2, x20⊕x1x2],	[x1⊕x10x2],
[x10⊕x1x20],	[x1x2],	[x10, x20],	[1].

Table 2

The four classes in P22 under the cmr-complexity.

[0, 1]	[x10x2,x1x20,x1⊕x2,x1⊕x20,x10⊕x1x2,x20⊕x1x2],
[x1,x2, x10,x20],	[x1x2,x1⊕x10x2,x10⊕x1x20,x10x20].

Table 3

Number of equivalence classes in P2n under transformation groups.

N	S2n	CM2n	MN2n	SB2n	SP2n
1	4	2	2	2	2
2	12	4	3	4	3
3	80	11	5	11	5
4	3984	∗	∗	74	11
5	37 333 248	∗	∗	∗	38

Table 4

Minor classification of ternary Boolean functions.

(i) CFkn≤CMkn;	(ii) Skn≤CMkn;	(iii) Skn≤NFkn;
(iv) NFkn²RAG;	(v) CMkn²RAG;	(vi) LGkn²MNkn;
(vii) CAkn²MNkn;	(viii) CAkn²NFkn;	(ix) LGkn²NFkn;
(x) CMkn²NFkn;	(xi) NFkn²MNkn.