Completeness for uniformly delayed circuits, a survey

Acta Applicandae Mathematicae 52: 49–61, 1998. c 1998 Kluwer Academic Publishers. Printed in the Netherlands.

49

Completeness for Uniformly Delayed Circuits, A Survey T. HIKITA Computer Science Department, Meiji University, 1-1-1 Higashi-Mita, Tama-ku, Kawasaki 214, Japan

I. G. ROSENBERG D´epartement de math. et stat., Universit´e de Montr´eal, Succursale Centre-Ville, Montr´eal, Qu´ebec, H3C 3J7, Canada (Received: December 1994) Abstract. We survey algebraic results on combinatorial circuits constructed from many-valued uniformly delayed gates. These involve the composition of uniformly delayed operations, the lattice of uniform clones, the corresponding relational theory, uniform completeness and the search for an effective completeness criterion. Mathematics Subject Classification (1991): 03B50. Key words: delayed operators, functional completeness, maximal incomplete classes, uniform completeness, uniform composition.

1. Introduction In this paper we survey algebraic problems and results arising from combinatorial circuits based on uniformly delayed manyvalued gates. They are modeled by uniformly delayed operations (f, δ) where f : An → A is an n-ary operation on the finite (input and output) alphabet and δ is a nonnegative integer delay. Such operations are composed in a restricted way. All variables of f are replaced by delayed operations of arbitrary arities but with the same delay. The composition closed sets of uniformly delayed operations containing all (eni , 0) where eni is the ith n-ary projection are called uniform clones. A polyrelation is an infinite sequence (ρ0 , ρ1 , . . .) of relations on A of the same arity. There is a natural concept of preservation of a polyrelation by a uniformly delayed operation. The Galois closed sets of uniformly delayed operations induced by this Galois connection are exactly the uniformly clones. We describe internally the Galois closed sets of polyrelations. There are several notions of completeness in the literature. The weakest one is called the uniform completeness. A general and effective criterion is known only for |A| = 2, 3. We report on the progress towards such criterion for arbitrary finite A. This seems to be a surprisingly complex problem.

VTEX(EL) PIPS No.: 156205 MATHKAP KALVB3.tex; 27/07/1998; 13:51; v.7; p.1

50

T. HIKITA AND I. G. ROSENBERG

Figure 1.

2. Preliminaries Switching circuits are built from basic hardware components which we shall henceforth call gates. For simplicity each gate (Figure 1) is a device with a single output and n inputs (n positive integer). The gate receives and emits signals in the same finite alphabet which will be identified with k := {0, . . . , k − 1}. If the signal on the ith input is xi (i = 1, . . . , n), then the response of the gate is a unique signal completely determined by the n-tuple (x1 , . . . , xn ) ∈ kn . Denoting this signal by f (x1 , . . . , xn ) we can describe the functioning of a gate by an nary operation f on k (i.e. a map from kn into k). Thus each gate carries an operation f describing its behavior. S (n) . Denote by O(n) the set of all n-ary operations on k and set O := ∞ n=1 O In real circuits the physical time dependent signal xi (t) on the ith input (i = 1, . . . , n) and the output signal x0 (t) are continuous functions of time. The real situation may be rather complex and so we approximate it by assuming that there are time invariant delays δ1 , . . . , δn such that for all t > 0


x0 (t) = f x1 (t − δ1 ), . . . , xn (t − δn )

(1)

(where xi (t) (i = 0, . . . , n) are maps from [0, ∞) into k). For simplicity we make the usual assumption that δ1 , . . . , δn ∈ N := {0, 1, . . .}. Quite often it is also assumed that δ1 = · · · = δn and such a gate is called uniformly delayed. (It is not clear to us whether this restriction is a mere convenience or imposed by some hardware or circuit property.) A uniformly delayed gate is fully described by the pair (f, δ) which we call a delayed operation. To model the complex behavior of a real gate by a delayed operation is already a considerable simplification. The model is nevertheless better than the standard one which altogether ignores the delays (and the related races and hazards). Propositional logic and universal algebra are adequate tools for the algebraic treatment of combinatorial circuits based on nondelayed gates. To handle such circuits based on uniformly delayed gates a new theory should be developed. Switching circuits are obtained from a collection of gates by attaching outputs of certain gates to inputs of other gates. We consider only combinatorial or feedback-free switching circuits. Such a circuit is in the shape of a rooted tree with gates at the internal vertices and external inputs (not necessarily pairwise

KALVB3.tex; 27/07/1998; 13:51; v.7; p.2

51

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

Figure 2.

distinct) at the leaves. (An example is in Figure 2 where f, g are binary and h, i, j unary operations.) In such a circuit the delays are clearly cumulative. If the circuit represents a uniformly delayed operation, the sum of delays along each branch from the root to a leaf should be constant (4 for the circuit in Figure 2). Remark 2.1. This is not absolutely necessary. In fact, if the composed operation (e.g. the operation f (g(h(x1 ), i(x2 )), j(x3 )) for the circuit in Figure 2) does not depend on a variable, then the sum of delays on the branch from the root to each of the leaves labeled by this variable may be arbitrary. In particular, if the composed operation is constant, its delay could be arbitrarily modified. However, this is rather academical because usually sources of constant signals are so easy to get and cheap that they can be taken for granted. Therefore we ignore this aspect in our theory. The following definitions are made to capture the requirement of the constant sum of delays on each branch. DEFINITION 2.2. Let f ∈ O(n) and let gi ∈ O(mi ) (i = 1, . . . , n). Set p := m1 + · · · + mn and define h = f (g1 , . . . , gn ) ∈ O(p) by setting for all x1 , . . . , xp ∈ k h(x1 , . . . , xp ) := f g1 (x1 , . . . , xm1 ), g2 (xm1 +1 , . . . , xm1 +m2 ), . . . ,
gn (xp−mn +1 , . . . , xp ) .

For δ, δ0 ∈ N and F := (f, δ), Gi := (gi , δ0 ) (i = 1, . . . , n) set


F ⊗ (G1 , . . . , Gn ) := f (g1 , . . . , gn ), δ + δ0 .

Denote by U the set O × N of all delayed operations. For a fixed n we can view ⊗ as a partial operation on U defined if F = (f, δ) where f is n-ary and all Gi have the same delay δ0 . This restriction differentiates our structure from universal algebras and propositional calculi of most logics in which an unrestricted composition is allowed.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.3

52

T. HIKITA AND I. G. ROSENBERG

DEFINITION 2.3. Let 1 6 i 6 n. The projection (trivial operation) eni is the n-ary operation on k such that eni (x1 , . . . , xn ) = xi for all x1 , . . . , xn ∈ k. A clone on k is a subset of O containing all projections and closed under . A uniform clone on k is a subset of U containing all (eni , 0) (1 6 i 6 n) and closed under ⊗. Remark 2.4. (1) Let C be a uniform clone on k and (f, δ) ∈ C . Due to the presence of (eni , 0) we also have (g, δ) ∈ C where g is obtained from f by (i) any permutation (= exchange) of variables, (ii) any identification (= fusion) of variables or (iii) the addition of a nonessential (= fictitious or dummy) variable. (2) The definition of a uniform clone can be modified. A uniform preiterative set is a subset of U closed under ⊗ and all variable exchange and fusions. Such a set is (i) a uniform iterative set if it is also closed under the addition of fictitious variables and (ii) unitary if it contains (e11 , 0). However, the relational theory and large ‘closed sets’ only involve uniform clones and so we do not pursue this topic any further here. (3) Denote by Lu the set of all uniform clones on k and set Lu := (Lu , ⊆). element of It is immediate that Lu is intersection closed and UV the greatest T Lu ; and therefore Lu is a complete lattice (in which i∈I Ci = i∈I Ci for all Ci ∈ Lu , i ∈ I ).

3. Polyrelations A subset ρ of kh is an h-ary relation on k. For n > 0 denote by ρ[n] the set of h × n matrices whose columns are all in ρ. For f ∈ O(n) and X ∈ ρ[n] let f [X] stand for the row vector (f (X1∗ ), . . . , f (Xh∗ )) where Xi∗ denotes the ith row of X and let f [ρ] := {f [X] : X ∈ ρ[n] }. We say that f preserves ρ if f [ρ] ⊆ ρ and put Pol ρ := {f ∈ O : f preserves ρ}. In universal algebra terms f preserves ρ means that ρ is a subuniverse of hk; f ih . The following result from [5] and [2] if there exist relations ρ1 , ρ2 , . . . is basic: A subset C of O is a clone if and only T on k such that Pol ρ1 ⊇ Pol ρ2 ⊇ · · · ⊇ C = ∞ i=1 Pol ρi . We extend this to uniform clones. DEFINITION 3.1. An infinite sequence ρ = (ρ0 , ρ1 , . . .) of h-ary relations on k is an h-ary polyrelation (or a temporal relation) on k. We say that (f, δ) ∈ U preserves an h-ary polyrelation ρ = (ρ0 , ρ1 , . . .) if f [ρi ] ⊆ ρi+δ for all i > 0. For each δ > 0 we set Podδ ρ := {f ∈ O : f [ρi ] ⊆ ρi+δ , i = 0, 1, . . . }, Pod ρ :=

∞ [

(Podδ ρ) × {δ}.

δ=0

KALVB3.tex; 27/07/1998; 13:51; v.7; p.4

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

53

EXAMPLE 3.2. Let 6 be an order (a reflexive, transitive and antisymmetric binary relation). Then M := Pol 6 is the set of 6-monotonic operations (i.e. f ∈ O(n) such that f (x1 , . . . , xn ) 6 f (y1, . . . , yn ) whenever x1 6 y1 , . . . , xn 6 yn ). Similarly, f ∈ O(n) is 6-antimonotonic if f (x1 , . . . , xn ) > f (y1 , . . . , yn ) whenever x1 6 y1 , . . . , xn 6 yn . Let A be the set of 6-antimonotonic operations and let µ := (6, >, 6, >, . . .). Then Podδ µ = M for all even δ, Podδ µ = A for all odd δ and Pod µ = (M × {0, 2, . . .}) ∪ (A × {1, 3, . . .}). Notice that Pod0 ρ =

T∞

i=0 Pol ρi

and that Pod ρ is a uniform clone [11, 24].

THEOREM 3.3. A subset C of U is a uniform clone if and only if there exist polyrelations ρ(1) , ρ(2) , . . . on k such that ∞ \

Pod ρ(1) ⊇ Pod ρ(2) ⊇ · · · ⊇ C =

Pod ρ(i) .

i=1

([24] Lemma 9 which gives, moreover, a construction of ρ(i) from C .) The relation ‘F preserves a polyrelation ρ’ induces a Galois connection (= polarity) between U and the set R of all polyrelations on k. Theorem 3.3 characterizes the Galois closed subsets of U as the uniform clones. The Galois closed subsets of R are the sets Ind X := {ρ ∈ R : every F ∈ X preserves ρ} for every X ⊆ U . To obtain an intrinsic description of these sets we need the following operations on the set R of all polyrelations. DEFINITION 3.4. (i) Let ξ be an h-ary relation on k. If h = 1 set ζ(ξ) = τ (ξ) = ∆(ξ) := ξ , else let ζ(ξ), τ (ξ) consist of all (a2 , . . . , ah , a1 ), (a2 , a1 , a3 , . . . , ah ) such that (a1 , . . . , ah ) ∈ ξ . Further set ∆(ξ) := {(a1 , . . . , ah−1 ) : (a1 , a1 , a2 , . . . , ah−1 ) ∈ ξ}, ∇(ξ) := {(a1 , . . . , ah+1 ) : (a1 , . . . , ah ) ∈ ξ, ah+1 ∈ k}.

(ii) Let ρ = (ρ0 , ρ1 , . . .) ∈ R. For λ ∈ {ζ, τ, ∆, ∇} set λ(ρ) := (λ(ρ0 ), λ(ρ1 ), . . .). Further set σ(ρ) := (ρ1 , ρ2 , . . .) (the shift of ρ). For µ = (µ0 , µ1 , . . .) ∈ R set ρ∩ µ := {ρ0 ∩ µ0 , ρ1 ∩ µ1, . . .). (Notice that ρ∩ µ = (∅, ∅, . . .) if the arities of ρ and µ are different.) The operations ζ, τ, ∆, ∇, σ and ∩ and their compositions were introduced and used in [7–9] cf. also [11]. (iii) We also used the following partial infinitary operation on R [24]. (i) (i) Let ρ(i) = (ρ0 , ρ1 , . . .) be h-ary polyrelations on k (i = 0, 1, . . .) satisfying (j+1)

ρ0

(j)

(j−1)

⊇ ρ0 ∪ ρ1

(0)

∪ · · · ∪ ρj

KALVB3.tex; 27/07/1998; 13:51; v.7; p.5

54

T. HIKITA AND I. G. ROSENBERG

for all j = 0, 1, . . . . The upper superposition of (ρ(0) , ρ(1) , . . .) is the polyrelation (0) (1) (ρ0 , ρ0 , . . .). A subset Y of R is a uniform coalgebra if Y is closed under ζ, τ, ∆, ∇, σ, ∩ and the upper superposition and Y contains the polyrelation ω ∗ := (ω, ω, . . .), where ω := {(x, x): x ∈ k}. By a clever application of the ideas from [2] Miliˇci´c proved the following fundamental result [24]: THEOREM 3.5. Let Y ⊆ R. Then Y = Ind X for some X ⊆ U if and only if Y is a uniform coalgebra. COROLLARY 3.6. Let ρ, λ ∈ R. Then Pod ρ ⊆ Pod λ if and only if λ can be constructed from {ρ, ω ∗ } by repeated applications of ζ, τ, ∆, ∇, σ, ∩ and the upper superposition.

4. Uniform Completeness Recall that a set X of operations on k is primal (or complete) if O is the least clone containing X (we use this terminology to avoid a possible confusion with the uniform completeness defined below). Whether a given X is complete is one of the first questions asked by an electrical engineer (if X is the set of operations realized by given gates) or by a logician (if X is the set of connections of a particular logic). For uniformly delayed operations the completeness concept is far from crisp and several types of completeness have been studied. In this section we discuss the most general – or weakest – one. DEFINITION 4.1. Let X ⊆ U . Denote by hXi the least uniform clone on k containing X . Call X uniform complete if for every f ∈ O the clone hXi contains (f, δ) for some δ > 0. This weak notion was introduced for k = 2 in [16, 17] (as the completeness of the second kind) and it captures the possibility of constructing each operation on k with some – perhaps very large – delay. The obvious objection is that realizing an operation with an enormous delay serves no purpose. However, it is the first approximation to the other completeness notions and the search for an effective uniform completeness criterion seems to pose a real challenge. In the historical retrospective the topic was introduced rather early by Kudryavtsev [16, 17] who defined the basic concepts and gave an effective completeness criterion for k = 2 which is the most important case for possible applications. Some of Kudryavtsev’s results were rediscovered in [21]. After this early Russian start the focus moved to Japan where Nozaki and his school took up and expanded the study of multiple-valued delayed circuits, to the extent that during the past 25 years all papers in this domain (with the

KALVB3.tex; 27/07/1998; 13:51; v.7; p.6

55

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

lone exception of [22]) were published by the Japanese school. For k > 2 the breakthrough came in Hikita and Nozaki’s 1977 paper [10] which reduced the problem to three more manageable types. The first case (type A) is directly solved by a primality criterion [34, 35] while the third case (type C) was solved by Hikita in 1979 [9]. Meanwhile Hikita also completely classified the ternary case [6]. Here is a (noneffective) uniform completeness criterion ([17] Theorem 4 for k = 2, [10, 22] for k > 2, cf. also [4] Theorem 7.6). For X ⊆ U , n > 1 and δ > 0 set U (n) := O(n) × N, X (n) := X ∩ U (n) ,

Xδ := {f : (f, δ) ∈ X},

X(δ) :=

∞ [

Xmδ .

m=0

Recall that the identity selfmap e := e11 of k satisfies e(x) = x for all x ∈ k. PROPOSITION 4.2. A uniform clone X is uniformly complete if and only if for some δ > 0 the set X(δ) is primal and e ∈ Xδ . To get an effective uniform completeness criterion we turn to polyrelations. DEFINITION 4.3. For an equivalence ε on {1, . . . , h} put ∆ε := {(a1 , . . . , ah ) ∈ kh : if iεj then ai = aj } (i.e. ∆ε consists of all h-tuples over k constant on each block of ε). The relations ∆ε are termed diagonal. The diagonal relation and ∅ are called trivial. It is well-known [1, 34, 35] that Pol λ = O iff λ is trivial. We say that a polyrelation ρ is proper if Pod ρ is uniformly incomplete. We characterize the improper polyrelations. PROPOSITION 4.4. A polyrelation ρ = (ρ0 , ρ1 , . . .) is improper if and only if (i) all ρi are trivial, or (ii) there are p > 0, m > 0 and trivial relations α0 , . . . , αp−1 such that ρi ⊆ ρi+p ⊆ · · · ⊆ ρi+mp = ρi+(m+1)p = · · · = αi for all i = 0, . . . , p − 1. Observe that there are many uniform clones Pod ρ distinct from U that are nevertheless uniformly complete. We say that ρ = (ρ0 , ρ1 , . . .) is periodic, if there is p > 0 such that ρi+p = ρp for all i > 0. For a periodic ρ the least p > 0 with this property is the period pρ of ρ. COROLLARY 4.5. Let ρ be a periodic polyrelation with period p. Then ρ is proper if and only if at least one ρi is nontrivial. DEFINITION 4.6. A clone M is maximal if M ⊂ M 0 ⊂ O (strict inclusions) for no clone M 0 . The maximal clones are completely known ([33] for k = 2, [12] for k = 3 and [34, 35] for k > 3). They are of the form Pol σ where the relation σ runs through 6 families.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.7

56

T. HIKITA AND I. G. ROSENBERG

DEFINITION 4.7. A uniformly incomplete uniform clone is uniformly precomplete if every uniform clone properly containing it is already uniformly complete (i.e. if it is a maximal element of the poset of uniformly incomplete uniform clones ordered by ⊆). A set Ξ of proper polyrelations is termed generic if each uniformly incomplete uniform clone G is contained in Pod ξ for some ξ ∈ Ξ. We gradually build smaller and smaller generic sets with the hope that finally we arrive at a generic set Ξ◦ such that Pod ξ is uniformly precomplete for every ξ ∈ Ξ◦ (and every uniformly precomplete uniform clone is of the form Pod ξ for some ξ ∈ Ξ◦ ). The system Ξ◦ would provide the best general completeness criterion in the sense that for a given subset F of U we only have to test whether F ⊆ Pod ξ for all ξ ∈ Ξ◦ . In other words, F would be uniformly complete exactly if F * Pod ξ for all ξ ∈ Ξ◦ . Observe that the existence of Ξ◦ is not a priori clear. The essential step is Hikita and Nozaki’s generic system Ξ0 [10]. DEFINITION 4.8. For a relation σ on k put σ ∗ := (σ, σ, . . .). We say that σ ∗ is of type A if Pol σ is a maximal clone. Proper periodic polyrelations of arity at most k are of type B. For the last type C0 we need the following special binary relations. An equivalence relation on a proper subset P of k distinct from {(p, p): p ∈ P } is called a proper partial equivalence on k. A binary polyrelation (ρ0 , ω, ω, . . .) is of type C0 if (1) ρ0 = {c} × k for some c ∈ k, or (2) ρ0 is a proper partial equivalence, or (3) ρ0 = {(a, s(a)): a ∈ P } where P ⊆ k and s is an injective map from P into k such that (i) if im s = P then s is a permutation of P of prime order and 6 P then s(p) ∈ P implies s(p) = p. (ii) if im s = Let Ξ0 consists of all polyrelations of type A, B and C0 . THEOREM 4.9 ([8, 10]). The set Ξ0 is generic. The uniform clones of types A and C0 are uniformly precomplete.

5. Generic Sets By Theorem 4.9, it remains to study the polyrelations of type B. Our first step is to restrict the arity h of the type B polyrelations to h = 1, 2 [11]. PROPOSITION 5.1. Let Ξ1 consists of all polyrelations of type A, of all unary and binary polyrelations of type B and all polyrelations of type C0 . The set Ξ1 is generic. We consider the unary polyrelations of type B.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.8

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

57

DEFINITION 5.2. Let p and r be positive integers. We say that r is a special divisor of p if p = pa1 1 · · · pal l ,

r = pb11 · · · pbl l ,

where p1 < · · · < pl are primes and ai and bi integers such that ai > bi > 0 for all i = 1, . . . , l. DEFINITION 5.3. Denote by N the set of all unary polyrelations ρ = (ρ0 , ρ1 , . . .) on k with period p for which there exists a special divisor r of p such that ρ0 , ρr , ρ2r , . . . , ρp−r are pairwise disjoint nonempty subsets of k while ρj = ∅ for all 0 < j < p not divisible by r . EXAMPLE 5.4. (1) Let k = 2. Since there are at most 2 disjoint nonempty subsets of 2 = {0, 1} – namely {0} and {1} – we have 1 < p/r 6 2; whence p/r = 2 and r = 2a , p = 2a+1 for some a > 0. Without loss of generality we can choose ρ0 := {0}, ρ2a := {1} and ρi := ∅ for all 0 < i < 2a+1 , i 6= 2a . For a = 0, 1, . . . the corresponding Pod ρ make up a countably infinite family of uniformly precomplete uniform clones on 2, cf. Kudryavtsev’s list in [16, 17]. (2) Let k = 3. Proceeding as in (1) one can find all the uniformly precomplete uniform clones of this type on 3 listed in [6]. DEFINITION 5.5. (1) For a selfmap s of k denote by s◦ the graph {(x, s(x)): x ∈ k} of s. (2) Denote by S the set of all polyrelations ρ = (ρ0 , ρ1 , . . .) of period p such that there exists a prime divisor q of k and a special divisor r of p satisfying either (i) (a) p0 := p/r is the least positive solution h of αh ≡ 1 (mod q ) for some 1 < α < q and (b) there exists a permutation s of k with k/q cycles of j length q such that ρjr = (sα )◦ for all j = 0, . . . , p0 − 1 while ρl = ∅ if r does not divide l, or (ii) q m divides k for some 1 < m < p and there exists α = (α0 , . . . , αm−1 ) ∈ qm such that α0 6= 0 and p is the least positive solution l of e1 Yαl = e1 where e1 := (1, 0, . . . , 0) ∈ qm and Yα is the m × m matrix 



0 1 0 ··· 0 0  0 0 1 ··· 0 0     .. ..   Yα =  . . .     0 0 0 ··· 0 1  α0 α1 α2 · · · αm−2 αm−1 Upon a suitable identification of k with the Cartesian product b × qm (where b := k/q m ) we have ρjr := s◦j for j = 0, . . . , p0 − 1 and ρl = ∅ for all 0 < l < p not divisible by r where sj (u, v) := (u, v ⊕ ej+1 ) for all 0 6 j <

KALVB3.tex; 27/07/1998; 13:51; v.7; p.9

58

T. HIKITA AND I. G. ROSENBERG

m (u ∈ b, v ∈ qm , ⊕ denotes the componentwise mod q addition on qm and e1 := (1, 0, . . . , 0), . . . , em := (0, . . . , 0, 1)) while for all m 6 j < p0 c

m−1 sj := sc00 ◦ · · · ◦ sm−1

with (c0 , . . . , cm−1 ) := e1 Yαj (for selfmaps u and v of k the selfmap u ◦ v is defined by (u ◦ v)(x) := v(u(x)) for all x ∈ k and u0 := e and un+1 := u ◦ un for all n > 0). A binary polyrelation ρ = (ρ0 , ρ1 , . . .) is reflexive if each ρi is reflexive (i.e. ω := {(x, x): x ∈ k} ⊆ ρi ). Let Ξ2 consist of N ∪ S , all binary reflexive polyrelations and of all polyrelations of type A and C0 . We have THEOREM 5.6. The set Ξ2 is generic. In the permutation group problems involved in the reduction of the areflexive binary polyrelations to the set S we were substantially helped by P. Frankl and also helped by P. P. P´alfy. DEFINITION 5.7. Let P denote the set of binary polyrelations ρ = (ρ0 , ρ1 , . . .) of period 2m (where m > 0) such that ρ0 is a bounded (partial) order 6 (i.e. 6 is reflexive, antisymmetric, transitive and there exist o, e ∈ k such that o 6 x 6 e for all x ∈ k), ρ2m−1 is the converse order > and ρj = ω for all 0 < j < 2m , j 6= 2m−1 . DEFINITION 5.8. A binary polyrelation ρ = (ρ0 , ρ1 , . . .) is symmetric if each ρi is symmetric (i.e. (a, b) ∈ ρi ⇒ (b, a) ∈ ρi ). Denote by M the set of all proper, binary symmetric and reflexive polyrelations. Let Ξ3 consists of N ∪ S ∪ P ∪ M and of all polyrelations of type A and C0 . THEOREM 5.9. The set Ξ3 is generic.

6. The Symmetric and Reflexive Binary Polyrelations DEFINITION 6.1. Let λ be a binary symmetric and reflexive relation on k. The center of λ is the set Cλ := {x ∈ k: {x} × k ⊆ λ}.

The relation λ is central if Cλ is a proper subset of k. Let ρ = (ρ0 , ρ1 , . . .) be a binary polyrelation. Call ρ central if ρ is periodic, each ρi is either central or equal k2 and at least one ρi is central. To avoid circles in the elimination process we use the following concept.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.10

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

59

DEFINITION 6.2. A polyrelation ρ ∈ M with period p is rich if every λ ∈ M such that Pod ρ ⊆ Pod λ satisfies (i) pλ > p and (ii) |λ0 | + · · · + |λp−1 | 6 |ρ0 | + · · · + |ρp−1 |

whenever pλ = p. In other words, among the polyrelations λ ∈ M with Pod λ ⊇ Pod ρ, the polyrelation ρ has the shortest possible cycle length p, and, moreover, among such polyrelations λ with cycle length p the polyrelation ρ has the largest possible sum of relation sizes. Thus the primary concern is the minimality of the cycle length while the maximality of the sum of cardinalities is the secondary one. DEFINITION 6.3. A set Σ = {ε0 , . . . , εr−1 } of equivalence relations on k is orthonormal if (i) for each 0 6 i < r all the blocks of εi have the same size and (ii) |B0 ∩ · · · ∩ Br−1 | = 1 whenever Bi is a block of εi for all i = 0, . . . , r − 1. If there is an orthonormal Σ on k then clearly k can be identified with a0 ×· · ·×ar−1 (whereby ai is the number of blocks of εi and εi is the kernel of the ith projection). Denote by E the set of all polyrelations ρ = (ρ0 , ρ1 , . . .) of period p > 1 for which there exists a divisor r of p and an orthonormal set {ε0 , . . . , εr−1 } of equivalence relations such that ρjr = εj for 0 6 j < p/r and ρj = k2 for 0 < j < p, j not divisible by r . DEFINITION 6.4. Denote by C the set of all rich central polyrelations ρ such that Pod ρ ⊆ Pod λ for no λ of type A. Let Ξ4 consist of N ∪ S ∪ P ∪ E ∪ C and all polyrelations of type A and C0 . THEOREM 6.5. The set Ξ4 is generic. Remark 6.6. (1) For k = 2, 3 the set E ∪ C is empty. We found several strong properties of polyrelations from C which seem to indicate that C may always be void. (2) We have not yet proved that for every ρ ∈ N ∪S ∪P ∪E the uniform clone Pod ρ is uniformly precomplete. This can be done in two ways: (i) one could prove that Pod ρ ∪ {F } is uniformly complete for every F ∈ U \ Pod ρ (by using the very special form of ρ, reducing it to a unary F and applying Proposition 4.2) or (ii) by showing that for each polyrelation λ such that Pod λ ⊃ Pod ρ the uniform clone Pod λ is uniformly complete. For this one can use the very special form of ρ and Corollary 3.6. (3) The proofs for the results surveyed here are quite long and have not yet been written in a preprint form. Some of the earlier results are in [11]. The remainder was obtained during the second author’s stay in Japan in the first half of 1991. The financial support provided by a J.S.P.S. grant and an N.S.E.R.C. exchange grant as well as the hospitality of Meiji University (Tokyo) and Electrotechnical Laboratory (Tsukuba) is gratefully acknowledged.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.11

60

T. HIKITA AND I. G. ROSENBERG

References 1. Ba˘ıramov, R. A.: On the question of functional completeness in many-valued logics (Russian), Diskret. Anal. 11 (1967), 3–20. 2. Bodnarchuk, V. G., Kaluzhnin, L. A., Kotov, V. N. and Romov, B. A.: The Galois theory for Post algebras I–II (Russian), Kibernetika (Kiev) 3 (1969), 1–10; 5 (1969), 1–9; English translation: Systems Theory Res. 3. 3. Birjukova, L. A. and Kudrjavcev, V. B.: On completeness of functions with delays (Russian), Probl. Kibernet. 23 (1970), 5–25; English translation: Systems Theory Res. 23 (1973), 3–24. 4. Dassow, J.: Completeness Problems in the Structural Theory of Automata, Akademie-Verlag, Berlin, 1981. 5. Geiger, D.: Closed systems of functions and predicates, Pacific J. Math. 27(1) (1968), 95–100. 6. Hikita, T.: Completeness criterion for functions with delay defined over a domain of three elements, Proc. Japan Acad. 54 (1978), 335–339. 7. Hikita, T.: Completeness properties of k-valued functions with delays: Inclusions among closed spectra, Math. Nachr. 103 (1981), 5–19. 8. Hikita, T.: Completeness criterion for delayed logic devices, Preprint, Univ. of Tokyo, 1972. 9. Hikita, T.: On completeness for k-valued functions with delay, in: B. Cs´ak´any and I. Rosenberg (eds), Coll. Math. Soc. J´anos Bolyai 28, Finite Algebra and Multiple-Valued Logic, NorthHolland, Amsterdam, 1981, pp. 345–371. 10. Hikita, T. and Nozaki, A.: A completeness criterion for spectra, SIAM J. Comput. 6 (1977), 285–297. Corrigenda, ibid. 8 (1979), 656. 11. Hikita, T. and Rosenberg, I. G.: Completeness for uniformly delayed circuits, Proceedings 13th Internat. Sympos. Multiple-Valued Logic, Kyoto, May 1983, IEEE (1983), pp. 2–10. Proofs: Preprint, Tokyo Metropolitan Univ., 1983. 12. Iablonski˘ı, S. V.: Functions constructions in the k-valued logic (Russian), Trudy Mat. Inst. Steklov. 51 (1958), 5–142. 13. Ibuki, K.: Study on the universal logic elements (Japanese), Electric Communication Laboratory Tech. Report 3747 (1968). 14. Ibuki, K., Namura, K. and Nozaki, A.: (Japanese) Trans. IECE 46 (1963), 934. 15. Kritshevskii, R. E.: The realization of functions by superpositions (Russian), Probl. Kibernet. 2 (1959), 123–138; German translation: Probl. Kybernet. 2 (1963), 139–159. 16. Kudryavtsev, V. B.: Completeness theorem for a class of automata without feedback couplings (Russian), Dokl. Akad. Nauk SSSR 132 (1960), 272–274; English translation: Soviet Math. Dokl. 1 (1960), 537–539. 17. Kudryavtsev, V. B.: Completeness theorem for a class of automata without feedback couplings (Russian), Probl. Kibernet. 8 (1962), 91–115; German translation: Probl. Kybernet. 8 (1965), 105–136. 18. Kudryavtsev, V. B.: The power of sets of precomplete sets for certain functional systems connected with automata (Russian), Probl. Kibernet. 13 (1965), 45–74. 19. Kudryavtsev, V. B.: On functional properties of logical nets (Russian), Math. Nachr. 55 (1973), 187–211. 20. Kudryavtsev, V. B.: Functional Systems (Russian), Monograph, I.M.U., Moscow, 1982. 21. Loomis, H. H., Jr.: Completeness of sets of delayed-logic devices, IEEE Trans. Elektron. Comput. EC-14 (1965), 157–172. 22. Martin, L., Reischer, C. and Rosenberg, I. G.: Completeness problems for switching circuits constructed from delayed gates, Proc. 8th Int. Symp. Multiple-Valued Logic, 1978, pp. 142–148. Electron. Informationsverarb. Kybernet. (in French) 19 (1983), 415, 171–186. An expanded French version appeared in Reseaux modulaires, Monographies de l.U.Q.T.R. No. 11, 1980, 91p. 23. Martin, N. M.: On the completeness of sets of gating functions with delay, in: Sympos. on Gating Algebra, Proc. Internat. Congr. Information Processing, Paris, 1959. 24. Miliˇci´c, M.: Galois connections for closed classes of functions with delays (Russian), Publ. de l’Inst. Math´ematique Nouvelle S´erie 36(50) (1984), Part I: 119–124, Part II: 125–136. 25. Miliˇci´c, M.: On Galois connections for one place functions with delays (Russian), Publ. de l’Inst. Math´ematique Nouvelle S´erie 44(58) (1988), 147–150.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.12

COMPLETENESS FOR UNIFORMLY DELAYED CIRCUITS

61

26. Nozaki, A.: R´ealisation des fonctions definies dans un ensemble fini a` l’aide des organes e´ l´ementaires d’entr´ee-sortie, Proc. Japan Acad. 46 (1970), 478–482. 27. Nozaki, A.: Functional studies of automata I–II, Sci. Papers College Gen. Ed. Univ. Tokyo 20 (1970), 21–36, 109–121. 28. Nozaki, A.: Complete sets of switching elements and related topics, First USA-Japan Computer Conference, 1972, pp. 393–396. 29. Nozaki, A.: Functional completeness of multi-valued logical functions under uniform compositions, Rep. Fac. Eng. Yamanashi Univ. 29 (1978), 61–67. 30. Nozaki, A.: Completeness criterion for a set of delayed functions with or without non-uniform compositions, in: B. Cs´ak´any and I. Rosenberg (eds), Coll. Math. Soc. J´anos Bolyai 28, Finite Algebra and Multiple-Valued Logic, North-Holland, Amsterdam, 1981, pp. 489–519. 31. Nozaki, A.: Completeness of logical gates based on sequential circuits (Japanese), Trans. IECE Japan J65-D (1982). 32. P¨oschel, R. and Kaluˇznin, L. A.: Funktionen-space und Relationenalgebren (German), VEB Deutscher Verlag der Wissenschaften, Berlin, 1979. 33. Post, E. L.: Introduction to a general theory of elementary propositions, Amer. J. Math. 43 (1921), 163–185. 34. Rosenberg, I. G.: La structure des fonctions de plusieurs variables sur un ensemble fini, C.R. Acad. Sci. Paris S´er. A–B 260 (1965), 3817–3819. ¨ 35. Rosenberg, I. G.: Uber die funktionale Vollst¨andigkeit in dem mehrwertigen Logiken (Struktur ˇ der Funktionen von mehreren Ver¨anderlichen auf endlichen Mengen), Rozpravy Ceskoslovensk´ e Akad. V˘ed., Ser. Math. Nat. Sci. 80 (1970), 3–93. 36. Rosenberg, I. G.: Completeness properties of multiple-valued logic algebras, in: D. C. Rine (ed.), Computer Science and Multiple-Valued Logic, Theory and Applications, North-Holland, Amsterdam, 1977, pp. 144–186. 2nd edition: ibid., 1984, pp. 150–194. 37. Rosenberg, I. G.: The multifaceted completeness problem of the structural theory of automata, Preprint CRMA-1197, Universit´e de Montr´eal, 1983.

KALVB3.tex; 27/07/1998; 13:51; v.7; p.13