Journal of Mathematical Sciences, Vol. 169, No. 4, 2010

AUTOMATA ALGEBRAS UDC 519.95

V. B. Kudryavtsev

Abstract. In this paper, we present the main results on problems of expressibility and completeness for automata theory, including the results for weakened problem statements.

Introduction The notion of an automaton is one of the most important notions in mathematics. It appeared at the junction of its different branches, as well as in engineering, biology, and other fields of science. From the content point of view, an automaton is a system with input and output channels. Its input channels receive sequential information which the automaton processes with regard to the structure of the sequence and gives it out through its output channels. These systems permit the interconnection of channels, leading to automata networks. The mapping of the input into output sequences is called an automaton function, and the possibility of such new mappings by means of combining automata led to the algebra of automata functions. The automata and their algebras began to be investigated in the 1930s, and most intensively since the 1950s. The foundations of the science were stated in the works of A. Turing, C. Shannon, E. Moore, S. Kleene, and other authors of the famous collection of papers Automata Studies [20]. The subsequent investigations of automata algebra were carried out under the great influence of the well-known article by Yablonskii on the theory of functions of k-valued logic [27]. The set of such functions can be considered as a set of automata without memory with the superposition operation on it. A number of problems were formulated for these functions, such as the problems of expressibility, completeness, bases, the problems of a closed-class lattice, and others. The well-developed technique of preserving predicates as the key one for solving these problems appeared. All this turned out to be very effective for the automata algebras which, in what follows, are referred to as functional systems. The expressibility is understood as the possibility of obtaining the functions of one set from functions of another set with the help of prescribed operations, and completeness means the expressibility of all functions in terms of the prescribed ones. In the review, the study of functional systems is carried out on a number of model objects, beginning with automata without memory, i.e., the functions of k-valued logic; then come automata with limited memory, i.e., such functions with delays, and finally we consider finite automata, i.e., automata functions of general form. Superpositions are used as operations, and in the last case, feedback is also used. The fundamental results of Post concerning the structure of the lattice of closed classes of Boolean functions are given for automata without memory. (It is not easy to become acquainted with these results today as the works which contain them [22, 28] have become a rarity.) Then the most essential results for the functions of k-valued logic are given. Their basis is formed by the approach developed by A. V. Kuznetsov and S. V. Yablonskii. The central idea of the approach is the concept of a precomplete class. For finitely generated systems of such functions, the family of precomplete classes forms a criterial system; in other words, an arbitrary set is complete exactly when it is not a subset of a precomplete class. The set of these precomplete classes turned out to be finite, and their characterization implies the Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 15, No. 4, pp. 37–66, 2009. c 2010 Springer Science+Business Media, Inc. 1072–3374/10/1694–0435 

435

algorithmic solvability of the completeness problem. Proceeding in this direction and describing explicitly all precomplete classes, Yablonskii solved the completeness problem for the functions of three-valued logic, and, together with Kuznetsov, found certain families of precomplete classes for an arbitrary finite-valued logic. Then, through the efforts of many researchers, new families of this kind were discovered in succession [16, 17, 19, 21, 30], and the conclusive constructions were implemented by Rosenberg [24]. A summary of these constructions is also given here. The limiting generalization of k-valued logic functions in the form of nonhomogeneous functions is also considered. For automata with limited memory, solutions of the completeness and expressibility problems are given as well as problems of weak versions of these assertions [12]. By an automaton of this kind, we mean a pair (f, t), where f is a function of k-valued logic and t is its calculation time. The weak completeness means the possibility of getting any function with some kind of delay from initial pairs with the help of superpositions. The case of functions of two-valued logic is considered in full detail. Here precomplete classes are also used as solving tools. In contrast to automata without memory, here the family of precomplete classes turned out to be countable. At the same time, the weak completeness problem remains algorithmically decidable. Another generalization of automata without memory is the class of linear automata with superposition and feedback operations. Here the situation is similar to the case of automata with limited memory. The description of the set of all precomplete classes is also possible; this set is countable, nevertheless, from this description the algorithm discerning the completeness of finite automata systems is deduced [9]. The transition to the general case of automata affords the opportunity to discover the continuum set of precomplete classes [14] and the algorithmic undecidability of the completeness problem [11]. Therefore, the search for ways of both weakening the completeness properties and, conversely, enriching this notion is of current importance. The first direction is realized by considering the problems of τ -completeness and A-completeness, which consist, respectively, of checking the possibility of generating all mappings on words of length τ and also such mappings for any fixed τ . The main results here are an explicit description of all τ - and A-precomplete classes and the algorithmic undecidability of the A-completeness problem [8]. The second direction is realized by stratifying all finite automata systems from the point of view of completeness and types. Each type is formed by all systems that contain a given Post class of automata without memory. The main result here is an explicit indication of the separability level of the algorithmically decidable cases of the automata systems on the Post diagram. This level turns out to be correct for the A-completeness case, too [6]. Together with the achievements in solving the main problems connected with expressibility and completeness, the review also outlines directions which are insufficiently or poorly developed. Only model cases of automata functional systems are dealt with here. The general constructions implemented by the author in [13] are not touched upon here. The author thanks A. V. Galatenko for his great help in preparing the article for publication. 1. Main Notions and Problems Let N = {1, 2, . . .}, and for h ∈ N , let

N0 = N ∪ {0},

N1 = N \ {1},

N1h = {1, 2, . . . , h}. Consider a set M and a mapping ω : M n → M , where M n is the nth Cartesian degree of the set M and n ∈ N . Let PM be the set of all such mappings ω for any n and Ω ⊆ PM . We consider the universal algebra M = (M, Ω), where M is called a carrier and Ω is a class of ¯ ⊆ M in the following way. ¯ (i) , i ∈ N , with a subset M operations. We associate a sequence of sets M 436

¯ (1) = M ¯ . Then the set M ¯ (i+1) consists of all elements m from M for which We assume that M ¯ (i) such that m = ω(m1 , m2 , . . . , mn ). We denote there exist ω from Ω and m1 , m2 , . . . , mn from M ∞  ¯ (i) . It is not difficult to see that IΩ is a closure operator on the set B(M ) formed by all ¯) = M IΩ (M i=1   ¯) ⊇ M ¯ , IΩ IΩ (M ¯ ) = IΩ (M ¯ ) are always fulfilled, subsets of the set M . Thus, for IΩ the conditions IΩ (M   ¯ ¯ ¯ ¯ , and M ¯ itself is and if M ⊇ M , then IΩ (M ) ⊇ IΩ (M ). The set IΩ (M ) is called the closure of the set M ¯ ). The set M ¯ is called closed if M ¯ = IΩ (M ¯ ). a generating set for IΩ (M ¯ is expressible in terms of M  if Let Σ(M) be the set of all closed subsets in M. We say that M  ¯ ¯ ¯ M ⊆ IΩ (M ). The set M is called complete if IΩ (M ) = M . The complete set is called a basis if any of its proper subsets is not complete. The main problems for M that will be of interest to us are the problems of expressibility and completeness as well as the problems on bases, on the lattice of closed classes, on their modification, and some other related questions. ¯ is expressible ¯ , M  ) such that M By the problem of expressibility we mean the indication of all pairs (M  in terms of M ; by the completeness problem we mean the indication of all complete subsets; the problem of bases is the description of all bases if they exist; the lattice problem is the construction of the lattice of all closed classes and the determination of its properties. Knowledge of the lattice Σ(M) gives the solution of the problems of expressibility and completeness. ¯ ) ⊆ IΩ (M  ). ¯ in terms of M  means the verification of the condition IΩ (M Thus, the expressibility of M For the solution of the completeness problem, the following scheme is used. A system Σ ⊆ Σ(M) is called criterial (a c-system) if for any set S ⊆ M , S is complete if and only if S is not a subset of any set M  , M  ∈ Σ . It is obvious that if Σ(M) \ {M } = ∅ (this will be assumed in what follows), then Σ(M) \ {M } = ∅ is a c-system. It is not difficult to see that dual atoms of the lattice Σ(M), which are also called precomplete classes, belong to any c-system. Let Σπ (M) be the set of all precomplete classes and Σπ¯ (M) be the set of all classes from Σ(M) that are not subsets of any precomplete class from Σπ (M). It is not difficult to verify that the following assertion holds. Proposition 1.1. The set Σπ (M) ∪ Σπ¯ (M) forms a c-system in the universal algebra M. Of special interest is the situation where Σπ¯ (M) is the empty set, since in this case the system Σπ (M) forms a c-system, which means that the completeness problem is reduced to the description of all precomplete classes. Let us mention an important case of this kind. A universal algebra M is called finitely generated if there exists a finite subset M  ⊆ M which is complete. The following assertion is known [10]. Proposition 1.2. If a universal algebra M is finitely generated, then Σπ (M) forms a c-system. We note that in the general case the converse is false. Now let us consider the case where the set M consists of functions. This is the main case for us. In this case, the universal algebra M is called a functional system. Let E be a set and let a function f have the form f : E n → E, where n ∈ N . Let U = {u1 , u2 , . . .} be the alphabet of variables with values in E, i ∈ N . To write a function f , we use the expression f = f (ui1 , ui2 , . . . , uin ). Denote the class of all such functions by PE . In order to avoid complex indices in variables ui , we use for them metasymbols x, y, and z, possibly with indices. Following Maltsev [18], we introduce in PE unary operations η, τ , Δ, and ∇, which are defined in the following way: (ηf )(x1 , x2 , . . . , xn ) = f (x2 , x3 , . . . , xn , x1 ), (τ f )(x1 , x2 , . . . , xn ) = f (x2 , x1 , x3 , . . . , xn ), (Δf )(x1 , x2 , . . . , xn ) = f (x1 , x1 , x2 , . . . , xn−1 ) if n > 1, 437

(ηf ) = (τ f ) = (Δf ) = f if n = 1, (∇f )(x1 , x2 , . . . , xn , xn+1 ) = f (x2 , x3 , . . . , xn+1 ). The form of these operations refines the operations from [14]. Let us introduce in PE a binary operation ∗ in the following way. For the functions f (x1 , x2 , . . . , xn ) and g(xn+1 , xn+2 , . . . , xn+m ) we assume that (f ∗ g)(x2 , x3 , . . . , xn , xn+1 , xn+2 , . . . , xn+m ) = (f (g(xn+1 , xn+2 , . . . , xn+m ), x2 , . . . , xn ). The described operations are called, respectively, shift, transposition, identification, extension, and substitution, and, in total, the operations of superposition. The set of these operations is indicated by Ωs . Let M ⊆ PE and IΩs (M ) = M . Then the functional system M = (M, Ωs ) is called the Post iterative functional system. 2. Functions of l-Valued Logic The functions from PE are called functions of l-valued logic if E = El = {0, 1, 2, . . . , l − 1}, l ≥ 2. In this case the symbol Pl is used instead of PE . The functional system Pl = (Pl , Ωs ) is considered to be one of the main models of the Post iterative functional system, the study of which served as the basis for the formulation of the problems and methods of functional system theory. If Ml = (M, Ωs ) and M ⊆ Pl , then M is called a Post functional system of type l. Let us briefly sum up the main results in the study of Pl that will be important for the consideration of the functional system of automaton functions. Post [22] gave a complete solution of the indicated problems on the completeness, expressibility, bases, and closed-class lattice for P2 . Let us describe this lattice preserving his notation. Consider the set Q of classes Ci , Ai , Dj , Lr , Os , St , Pt , Fvm , Fv∞ , where i = 1, 2, 3, 4, j = 1, 2, 3, r = 1, 2, 3, 4, 5, s = 1, 2, . . . , 9, t = 1, 3, 5, 6, v = 1, 2, . . . , 8, and m = 1, 2, . . . . The functions from P2 are called Boolean functions. Post denoted the class P2 by C1 . The class C2 contains all Boolean functions f such that f (1, 1, . . . , 1) = 1; C3 is the class of all Boolean functions such that f (0, 0, . . . , 0) = 0; C4 = C2 ∪ C3 . We say that a Boolean function f is monotonic if the inequalities ai ≤ bi for all i = 1, 2, . . . , n imply that f (a1 , . . . , an ) ≤ f (b1 , . . . , bn ). The class A1 consists of all monotonic Boolean functions; A2 = C2 ∩ A1 ; A3 = C3 ∩ A1 ; A4 = A2 ∩ A3 . The class D3 consists of all x1 , . . . , x ¯n ), where the Boolean function x ¯ is called the Boolean functions f such that f (x1 , . . . , xn ) = f¯(¯ negation and ¯0 = 1, ¯ 1 = 0; D1 = C4 ∪ D3 ; D2 = A1 ∪ D3 . The class L1 consists of all Boolean functions f (x1 , . . . , xn ) = x1 + x2 + · · · + xn + α (mod 2), α ∈ E2 ; L2 = C2 ∩ L1 ; L3 = C3 ∩ L1 ; L4 = L2 ∩ L3 ; L5 = D3 ∩ L1 . The class O9 consists of all Boolean functions depending essentially on no more than one variable; O8 = A1 ∩ O9 ; O4 = D3 ∩ O9 ; O5 = C2 ∩ O9 ; O6 = C3 ∩ O9 ; O1 = O5 ∩ O6 ; O7 = {0, 1}; O2 = O5 ∩ O7 ; O3 = O6 ∩ O7 . The class S6 consists of all Boolean functions of the form x1 ∨ x2 ∨ · · · ∨ xn and of constants; S3 = C2 ∩ S6 ; S5 = C3 ∩ S6 ; S1 = S3 ∩ S5 . The class P6 consists of all Boolean functions of the form x1 ∧ x2 ∧ · · · ∧ xn and constants; P5 = C2 ∩ P6 ; P3 = C3 ∩ P6 ; P1 = P3 ∩ P5 . We say that a Boolean function satisfies the condition aμ , μ ∈ N1 , if any μ collections at which it equals 0 have a common coordinate 0. The property Aμ is determined similarly with the change of 0 to 1. The class F4μ consists of all Boolean functions with the property aμ ; F1μ = C4 ∩ F4μ ; F3μ = A1 ∩ F4μ ; F2μ = F1μ ∩ F3μ . The class F8μ consists of all Boolean functions with the property Aμ ; F5μ = C4 ∩ F8μ ; F7μ = A3 ∩ F8μ ; F6μ = F5μ ∩ F7μ . A Boolean function satisfies the condition a∞ if all the collections at which it equals 0 have a common coordinate 0. The property A∞ is introduced by analogy with the change of 0 to 1. The class F4∞ consists of all Boolean functions with the property a∞ ; F1∞ = C4 ∩ F4∞ ; F3∞ = A1 ∩ F4∞ ; F2∞ = F1∞ ∩ F3∞ . The class F8∞ consists of all Boolean functions with the property A∞ ; F5∞ = C4 ∩ F8∞ ; F7∞ = A3 ∩ F8∞ ; F6∞ = F5∞ ∩ F7∞ . 438

Theorem 2.1 (see [22]). For the Post functional system P2 the following assertions are true: (a) the set of all closed classes in P2 is countable and coincides with the set Q; (b) the classes from Q form the inclusion lattice given in Fig. 1; (c) every closed class in P2 has a basis, and its power is always no more than 4; (d) the problems of completeness and expressibility for a Post functional system of type 2 applied to finite sets of Boolean functions are algorithmically decidable.

Fig. 1. Post lattice. Theorem 2.2. The structure on inclusion of classes from Q looks like that specified in Fig. 1. The properties of a Post functional system of the type l, l > 2, turned out to be more complex, which follows from the assertions given below. (n) Denote by Pl the set of all functions from Pl depending on no more than n variables u1 , u2 , . . . , un . n (n) (n) It is clear that the number of functions in Pl is equal to ll . Let Sln be the set of all functions from Pl each of which is equal to ui for some i, i = 1, 2, . . . , n. If M ⊆ Pi and M is finite, then α(M ) indicates the greatest number of variables of functions from M . 439

For a finitely generated Post functional system M of type l, let α(M) be the smallest number α α(M) such that IΩs (M  ) = M and α(M  ) = α for some M  ⊆ M . A nonempty set M  ⊆ Pl ∩ M is α(M) α(M)    α(M) called an R-set in M if IΩs (M ) ∩ Pl = M and M = Pl , and it is denoted by R . Let α(M) α(M) α(M) α(M) =R ∪ Sl . We say that a function f (x1 , x2 , . . . , xn ) from Pl preserves R if for any R α(M) α(M) we have f (g1 , g2 , . . . , gn ) ∈ R . The class of all collection of functions g1 , g2 , . . . , gn from R functions from M preserving Rα(M) is denoted by U Rα(M) . An R-set Rα(M) is called maximal if there    α(M)  α(M) ⊂ U Rα(M) .  such that U R1 is no R-set R1  Let R(M) be the set of all maximal R-sets and U R(M) be the set of all classes of preservation of elements from R(M). A Post functional system M is called trivial if M = IΩs (Sk1 ) or M = IΩs ({c(x)}), where c(x) = c, c ∈ El . The cardinality of a set A is denoted by |A|. Theorem 2.3 (see [13]). If a Post functional system M = (M, Ωs ) of type l is nontrivial and finitely generated, then   (a) U R(M) = Σπ (M);    α(M ) ; (b) U R(M )  ≤ 2Pl (c) R(M) is constructed effectively. This theorem is a development of an assertion from [27]. Corollary. The completeness problem for a finitely generated Post functional system of type l is algorithmically decidable for any l. Theorem 2.4 (see [13]). The expressibility problem for finite sets of a finitely generated Post functional system of type l is algorithmically decidable for any l. Theorem 2.5 (see [29]). For every l ≥ 3 there exists a Post functional system of type l such that (a) the Post functional system has a countable basis; (b) the Post functional system has a basis of an assigned finite power ; (c) the Post functional system has no basis. Corollary (see [29]). For every l ≥ 3, the lattice of closed classes in the Post functional system Pl is the continuum set. As was established in [27], the Post system Pl is finitely generated; therefore Theorems 2.3   functional and 2.4 are valid, and for the set U R(Pl ) its explicit description is found. It is more convenient for us to present it in a predicate form. Let ρ(y1 , y2 , . . . , yh ) be an h-ary predicate, the arguments of which take values from El . If ρ(a1 , a2 , . . . , ah ) = a, then for a = 1 the collection is called true, and for a = 0 it is false. The set of all true collections is denoted by ρ1 , and the set of false ones, by ρ0 . We say that a function f (x1 , x2 , . . . , xn ) from Pl preserves ρ if the truth of every element ρ(a11 , a12 , . . . , a1h ), ρ(a21 , a22 , . . . , a2h ), . . . , ρ(an1 ,n2 , . . . ,nh ) implies the truth of

  ρ f (a11 , a12 , . . . , a1h ), f (a21 , a22 , . . . , a2h ), . . . , f (an1 ,n2 , . . . ,nh ) . A set M of functions from Pl preserves ρ if every function from M preserves ρ. The class of all functions preserving ρ is denoted by U (ρ). Let us describe six special families of predicates. Family Post. Let the truth region of a predicate ρ(y1 , y2 ) be the diagram of a permutation σ(x) from Pl , which is decomposed into the product of cycles of equal prime length p, p ≥ 2. The family P consists exactly of all such predicates. Family E. Let El = E 1 ∪ E 2 ∪ · · · ∪ E t , where 1 ≤ t ≤ l, E i ∩ E j = ∅ for i = j. We consider the predicate ρ(y1 , y2 ) that is true precisely on collections for which a, b ∈ E i for some i. The family E consists exactly of all such predicates for the decompositions indicated. 440

Family L. Let l = pm , where p is prime, G = El , + be an Abelian group each of whose nonzero elements has order p, i.e., G is an elementary p-group. For p = 2, we consider the predicate ρG (y1 , y2 , y3 , y4 ), which is true exactly on collections for which y1 + y2 = y3 + y4 . In this case, L consists exactly of predicates ρG that correspond to all indicated elementary 2-groups G. For p = 2, we consider the predicate ρG (y1 , y2 , y3 ), which is true exactly on collections for which y3 = 2−1 (y1 + y2 ), where 2−1 denotes the number from Ep for which 2 · 2−1 ≡ 1 (mod p). In this case, L consists exactly of predicates ρG that correspond to all indicated elementary p-groups. Family B. Let h and m be natural numbers such that h ≥ 3, m ≥ 1, hm ≤ l, and let ϕ(x) be an arbitrary mapping of El into Ehm . Let a ∈ Ehm . Denote by [a]l the lth coefficient in the decomposition a=

m−1 

[a]l hl ,

[a]l ∈ Ehm .

l=0

We consider the predicate ρ(y1 , y2 , . . . , yh ) which is true exactly on collections for which the collection ([ϕ(a1 )]l , [ϕ(a2 )]l , . . . , [ϕ(ah )]l ) is nondifferent-valued for any l from Em , i.e., ρ is determined by the triple (h, m, ϕ); in addition, if ϕ(x) = x, then ρ is called elementary. The family B consists exactly of the predicates ρ determined by all the triples (h, m, ϕ) indicated. Family Z. A predicate ρ(y1 , y2 , . . . , yh ), h ≥ 1, is reflexive if its truth follows from the nondifferentvaluedness of the collection of values of the variables, and it is symmetrical if for any substitution t(u) of the numbers 1, 2, . . . , h we have   ρ(y1 , y2 , . . . , yh ) = ρ yt(1) , yt(2) , . . . , yt(h) . The nonempty set of all elements c from El such that for all values of the variables ρ(y1 , y2 , . . . , yh−1 , c) = 1 is called the center of the symmetrical predicate ρ. A predicate ρ is called central if it is symmetrical, reflexive, and has a center C such that C ⊂ El . The family Z consists exactly of all the central predicates ρ(y1 , y2 , . . . , yh ) such that 1 ≤ h ≤ l − 1. Family M . A partial order on El with one the greatest and one the smallest element can be assigned by a binary predicate ρ(y1 , y2 ). The family M consists exactly of all such predicates. Let W =P ∪E∪L∪B∪Z ∪M and let U (W ) consist of all classes of functions preserving predicates from W . Theorem 2.6. The following relations are true: (a) U (W ) = Σ(Pi ); l−1     (b) |U (W )| ∼ l · l − 2 · 2l + 1 · 2([(l−1)/2]) as l → ∞. Part (a) of this assertion was gradually established by the authors of [16, 17, 19, 21, 22, 24, 28, 30], and the concluding study was carried out in [24]. Part (b) was established in [31]. The sharp difference in the properties of P for l = 2 and l > 2 led to the study of different variations of the main problems for a Post functional system such as testing the completeness of a system of functions with assigned properties, like, for example, the Slupecki system, which contains all one-place functions, or examining the structure of fragments of the lattice of closed classes, etc. Moreover, the objects of scientific investigation were generalizations of Pl in the form of a Post functional system of nonhomogeneous functions, i.e., of functions depending on groups of variables whose domains of definition are different [13], and also functions whose variables, like the functions themselves, take a countable number of values. 3. Nonhomogeneous Functions The Post functional system PΣ = (PΣ , Ω) is a modification of l-valued logic. Let us define the class PΣ . Let Σ = (Σ1 , Σ2 ), where Σ1 = {A1 , A2 , . . . , As }, Σ2 = {B1 , B2 , . . . , Bt }, Ai = {ai1 , ai2 , . . . , airi }, 441

Bj = {bj1 , bj2 , . . . , bjrj }, Ai = Ak , Bj = Bl for i = k and j = l, and let Xi = {xi1 , xi2 , . . . , xin , . . .}, 1 ≤ i, B

k ≤ s, 1 ≤ j, l ≤ t. The set Xi contains variables with values from Ai . Let PΣ j be the set of all functions f (x11 , x12 , . . . , x1n1 , x21 , x22 , . . . , x2n2 , . . . , xs1 , xs2 , . . . , xsns ) with values from Bj . Denote the set

t  j=1

B

PΣ j as PΣ . The elements of PΣ are nonhomogeneous functions.

Operations forming the set Ω are natural generalizations of the operations η, τ , Δ, ∇, and ∗ from l-valued logic. The range of function g will be denoted as gˆ. Each operation from O, O ∈ {η, τ, ∇, Δ}, is replaced by the collection of operations O1 , O2 , . . . , Os . This replacement constructed in such a way that Oi acts like the operation O on the variable set Xi of the function f . The operation ∗ is also replaced by the collection of operations ∗ij in such a way that for functions f (x11 , x12 , . . . , x1n1 , x21 , x22 , . . . , x2n2 , . . . , xs1 , xs2 , . . . , xsns ) and

g(x11 , x12 , . . . , x1m1 , x21 , x22 , . . . , x2m2 , . . . , xs1 , xs2 , . . . , xsms ) B

applicability of the operation ∗ij means that g ∈ PΣ j and gˆ ⊆ Ai . The result of application of the operation ∗ij to the functions f and g is the function h(x11 , x12 , . . . , x1m1 +n1 , x21 , x22 , . . . , x2m2 +n2 , . . . , xs1 , xs2 , . . . , xsms +ns ) i−1 i−1 = f (x1m1 +1 , x1m1 +2 , . . . , x1m1 +n1 , . . . , xi−1 mi−1 +1 , xmi−1 +2 , . . . , xmi−1 +ni−1 ,

g(x11 , x12 , . . . , x1m1 , x21 , x22 , . . . , x2m2 , . . . , xs1 , xs2 , . . . , xsms ), i+1 i+1 s s s ximi +1 , . . . , ximi +ni −1 , xi+1 mi +1 , xmi +2 , . . . , xmi+1 +ni+1 , . . . , xms +1 , xms +2 , . . . , xms +ns ).

Consequently, PΣ = PΣ , η1 , η2 , . . . , ηs , τ1 , τ2 , . . . , τs , ∇1 , ∇2 , . . . , ∇s , Δ1 , Δ2 , . . . , Δs , ∗11 , ∗12 , . . . , ∗st . Operations in PΣ are called superposition operations (by analogy with l-valued logic). It is natural to consider that |Ai | > 1, |Bj | > 1, Bj ⊆ Bl for all i, j, l, j = l for PΣ . By analogy with l-valued logic, define the notions of closing, closed set, complete set, and precomplete set for PΣ . The closing operation will be denoted by JΩc . Theorem 3.1. The set of precomplete classes in PΣ is finite and can be constructed efficiently. Theorem 3.2. The algorithm that for any PΣ and any finite set M ⊆ PΣ checks whether M is complete in PΣ exists. Theorem 3.3. (a) PΣ is correct if and only if there exist Ai in Σ1 and Bj in Σ2 such that |Ai ∩ Bj | ≥ 2. (b) PΣ contains all precomplete and closed classes which are not equal to PΣ and not contained in any precomplete class if and only if for all satisfiable Ai ∈ Σ1 and Bj ∈ Σ2 , |Ai ∩ Bj | ≤ 1 and there exist Ai ∈ Σ1 and Bj  ∈ Σ2 such that |Ai ∩ Bj  | = 1. (c) PΣ does not contain precomplete classes if and only if for all satisfiable Ai ∈ Σ1 and Bj ∈ Σ2 , Ai ∩ Bj = ∅. Theorem 3.4. PΣ is finitely generated if and only if PΣ is correct. A complete set M ⊆ PΣ is called a basis if any of its proper subsets is not complete. Theorem 3.5. PΣ has a basis if and only if PΣ is finitely generated. Theorem 3.6. The minimum cardinality of a basis in PΣ is equal to |Σ2 |. 442

Theorem 3.7. The cardinality of the set of all closed classes in PΣ is equal to continuum if and only if Σ = ({{a, b}}, {{a, b}}), where a = b. A closed set M ⊆ PΣ is called open-closed if its complement is closed. By definition, the empty set is considered as closed. Let us describe all open-closed sets in PΣ . Define the equivalence relation R on Σ2 . Bj R Bj  if and only if there exists a sequence Bj1 , Bj2 , . . . , Bjl of elements Bju from Σ2 such that Bj1 ∩ Bj = ∅, Bjl ∩ Bj  = ∅ and for all p, 1 ≤ p ≤ l − 1, Bjp ∩ Bjp+1 = ∅ holds. Let E1 , E2 , . . . , Eq be the corresponding equivalence classes. If f ∈ PΣ , then denote by Kf the set of all functions g from PΣ such s   t   ∩ . Elements that f can be obtained from g by conjugating and renaming its variables. Let C = i=1

j=1

of a nonempty set C will be called absolute constants. Let Q be the set of all functions f from PΣ that depend only on the variables x11 , x21 , . . . , xs1 ; Q ⊆ Q; C  ⊆ C, and let every Ai contain no more than one absolute constant. Denote by C  (Q ) the set of all functions from Q that can be obtained from functions from the set Q by substitution of absolute constants from C  instead of all variables. Let Q ⊆ C  (Q), denote by (C  )−1 (Q ) the set of all functions f from Q for which C  ({f }) ⊆ Q (instead of C  ({f }) we will use the notation C  (f ), interpreting it like a function, from which the set C  ({f })) is composed. In the case where C  = ∅, by definition C  (Q ) = Q = (C  )−1 (Q ). Theorem 3.8. The set M ⊆ PΣ is open-closed if and only if (a) if any Aicontains no more than one absolute constant, then for some set S ⊆ C(Q), the relation Kf holds; M= f ∈C −1 (S)

(b) if some Ai contains more than one absolute constant, then for some set T ⊆ {1, 2, . . . , q}, the   B PΣ j holds. relation M = r∈T Bj ∈Er

Theorem 3.9. The completeness problem for the Post functional system PΣ is algorithmically solvable. This result was obtained in [13]. The completeness problems for PΣ for small cardinalities Σ1 and Σ2 was also solved in [13]. 4. Functions with Delays Let f (x1 , x2 , . . . , xn ) ∈ Pl and t ∈ N0 . A pair (f (x1 , x2 , . . . , xn ), t) is called a function f with delay t ˜ ˜ and the set of all such pairs is denoted  by Pl . We extend the operations η, τ , Δ, and ∇ to Pl , assuming that if μ is any of them, then μ (f, t) = (μ(f ), t). We introduce one more operation ∗s that is called a synchronous substitution, assuming that for the pairs (f, t), (f1 , t ), (f2 , t ), . . . , (fn , t ) in which the sets of variables of the functions f1 , f2 , . . . , fn are mutually disjoint the relation   (f, t) ∗s (f1 , t ), (f2 , t ), . . . , (fn , t ) = (f (f1 , f2 , . . . , fn ), t + t ) holds. The set of operations η, τ , Δ, ∇, and ∗s is denoted by Ωss and is called the operations of synchronous superposition. Let M ⊆ P˜l and JΩss (M ) = M ; then the functional system M = (M, Ωss ) is called an iterative Post functional system of functions with delays of type l. Let us briefly sum up the main results in the study of these functional system [12, 13]. Theorem 4.1. For a finitely generated Post functional system M of functions with delays of type l, the set Σπ (M) is finite and is effectively constructed for any l. Theorem 4.2. For a finitely generated Post functional system of functions with delays of type l, the problems of completeness and expressibility are algorithmically decidable for any l. Theorem 4.3. For every l from N1 there exists a Post functional system of functions with delays of type l such that 443

(a) there is a countable basis; (b) there is a finite basis of an assigned power ; (c) there is no basis. Corollary. The lattice of closed classes in P˜l has cardinality of continuum for any l. An example of a finitely generated Post functional system of functions with delays is P˜l = (P˜l , Ωss ). For P˜l Theorem 4.1 can be refined as follows. Denote by M (1) the set of all functions f such that (f, t) ∈ M for some t.   Theorem 4.4. A set M ⊆ P˜l is complete in P˜l if and only if JΩs M (1) = P˜l , and M ⊇ {(f, 1)}, where f∈ / El . Let M = (M, Ωss ) and M  ⊂ M . We say that M  is weakly complete in M if for any function f from M (1) there is t such that (f, t) ∈ JΩss (M  ). The set M  is called weakly precomplete if it is not weakly complete but turns into such by adding any pair from M \ M  . The class of all such sets is denoted by ΣWπ (M). A class Σ is called weakly criterial if the set M  is weakly complete if and only if M   T for any T from Σ. It is obvious that for any weakly criterial system K the inclusion K ⊇ Σ(M) is true. Theorem 4.5. For a finitely generated Post functional system of functions with delays M = (M, Ωss ) of type l, the following assertions are true: (a) the set ΣWπ (M) is finite or countable; (b) the set ΣWπ (M) is weakly criterial ; (c) the set ΣWπ (M) is constructed effectively. Theorem 4.6. For a finitely generated Post functional system of functions with delays of type l the problem of weak completeness is algorithmically decidable for any l. An explicit description of the set ΣWπ (M) is obtained only for l = 2, 3 [9, 12]. Let us give here the description of the case l = 2. ˜ the set of all pairs (f, t) such that Let M ⊆ P2 and M ∈ {C2 , C3 , D3 , A1 , L1 }. We denote by M f ∈ M and t ∈ N0 . A function f (x1 , x2 , . . . , xn ) from P2 is called an α−, β−, γ−, or δ-function if f (x, x, . . . , x) is equal to x, 1, 0, or x ¯, respectively. Let A, B, Γ, and D be the classes of all α-, β-, γ-, or δ-functions, respectively. Denote by C˜ the set of all pairs of the form (f, t + 1), (ϕ, t + 1), (ψ, 0), where f ∈ B, ϕ ∈ Γ, ψ ∈ A, and t ∈ N0 . ˜i the set of all pairs of the form (f, 0), (¯ı, t + 1), (i, t), where f ∈ Ci+2 , Let i ∈ {0, 1}. We denote by E t ∈ N0 . x1 , x ¯2 , . . . , x ¯n ). A function f is called even if f (x1 , x2 , . . . , xn ) = f (¯ ˜ be the set of all pairs of the form (f, 0), (ϕ, t + 1), where Let Y be the set of all even functions. Let H ϕ ∈ Y , f ∈ D3 , and t ∈ N0 . For every r from N0 , we denote by Z˜r the set of pairs of the form (f, (2t + 1)2r ), (ϕ, (2t + 1)2s ), (ψ, 0), where f ∈ D, ϕ ∈ A, ψ ∈ A, t ∈ N0 , and s ∈ N0 \ {0, 1, 2, . . . , r}. ˜ r the set of all pairs of the form (f, (2t + 1)2r ), (0, t), (1, t), For every r from N0 , we denote by W (ϕ, (2t + 1)2s ), (ψ, 0), where f¯ ∈ M , ϕ ∈ M , ψ ∈ M , t ∈ N0 , and s ∈ N0 \ {0, 1, 2, . . . , r}. Let ˜ 3 , A˜1 , L ˜ 1 , C, ˜ E ˜0 , E ˜1 , H, ˜ Z˜0 , Z˜1 , . . . , W ˜ 0, W ˜ 1 , . . .}. ˜ = {C˜2 , C˜3 , D W ˜ holds. Theorem 4.7 (see [12]). The equality ΣWπ (P˜2 ) = W ˜ for any l exists only in the form of separate We note that an explicit description of ΣWπ (P˜1 ) = W families of weakly precomplete classes [1, 13]. From the content point of view, the modifications of the problem of completeness for a Post functional system of functions with delays considered in [13] are of interest. 444

5. Automata Functions The extension of the functions of l-valued logic to functions with delays is intermediate in the transition to the class of automaton functions, whose properties logically look substantially more complex than those of functions with delays. In order to introduce the notion of automaton function, we shall need auxiliary notations and definitions. Let C be a finite or countable set which is called an alphabet. A sequence of letters from C is called a word if it is finite and a superword if it is infinite. The class of all such words is denoted by C ∗ , and ¯ The word formed by the first r letters that of all superwords by C ω . Let C¯ = C ∗ ∪ C ω and ξ ∈ C. from ξ is called a prefix for ξ and is denoted by ξ]r . Let A and B be alphabets and f : A∗ → B ∗ . If ξ = c(1)c(2) . . . c(r), then r is called the length of the word ξ and is denoted by ξ. Let A and B be alphabets and f : A∗ → B ∗ . The function f is called determined if for any ξ from A∗ the equality f (ξ) = ξ is valid, and for any ξ1 and ξ2 from A∗ and any i such that 1 ≤ i ≤ min(ξ1 , ξ2 ), if ξ1 ]i = ξ2 ]i , then f (ξ1 )]i = f (ξ2 )]i . It is known that a determined function f can be recurrently represented by the so-called canonical equations of the form ⎧ ⎪ ⎨q(1) = q0 ,   (1) q(t + 1) = ϕ q(t), a(t) ,   ⎪ ⎩ b(t) = ψ q(t), a(t) , t = 1, 2, . . . , where the parameter q is called a state of f and takes values from the alphabet Q. This recurrence is determined in the following way. If α ∈ A∗ , β ∈ B ∗ , κ ∈ Q and α = a(1)a(2) . . . a(r),

β = b(1)b(2) . . . b(r),

κ = q(1)q(2) . . . q(r),

then for f (α) = β the word β is inductively calculated by α in the following way:   (a) b(1) = ψ q(1), a(1) , where q(1) = q0 ;     (b) if q(t) is calculated for 1 ≤ t ≤ r − 1, then q(t + 1) = ϕ q(t), a(t) and b(t) = ψ q(t), a(t) . It is often assumed that the alphabets A and B are Cartesian degrees of El , i.e., A = (El )n and B = (El )m , where n,m, p ∈N . In that case ∗ it is convenient to turn from a one-place determined function ∗ n m → (El ) to an n-ary determined function f (x1 , x2 , . . . , xn ) of the form f (x) of the form f : (El )   n m in the following way. f  : (El )∗ → (El )∗ Let ζ n ∈ (Ek∗ ) and f (ζ n ) = ζ  m , where ζ n = cn (1)cn (2) . . . cn (r),

ζ

m

m

m

m

= c (1)c (2) . . . c (r);

in addition,

    m cn (t) = e1 (t), e2 (t), . . . , en (t) , c (t) = e1 (t), e 2 (t), . . . , e m (t) , where 1 ≤ t ≤ r. Let ζi = ei (1)ei (2) . . . ei (r), ζj = ej (1)ej (2) . . . ej (r), where 1 ≤ i ≤ n and 1 ≤ j ≤ m. Now we assume that f  (ζ1 , ζ2 , . . . , ζn ) = (ζ1 , ζ2 , . . . , ζn ).

The function f  is obtained actually from f only at the cost of presenting the matrices formed by vector-letters (rows) of words ζ n and, respectively, ζ  m as matrices formed by the columns. Canonical equations (2) for f  are obtained from (1) by replacing all the parameters there with the corresponding vector values, i.e., ⎧ ⎪q(1) = q0 , ⎨   (2) q(t + 1) = ϕ q(t), e1 (t), . . . , en (t) ,   ⎪ ⎩ bj (t) = ψ q(t), e1 (t), . . . , en (t) , t = 1, 2, . . . , j = 1, 2, . . . , m. The function f  is considered to be an interpretation of f and is called an automaton function. 445

x1

x2 ? ?

xn ...

?

F ... y1 ? ?y2

?ym

Fig. 2. Automata illustration. The parameters n and m are called, respectively, the locality and dimensionality of the automaton function, and the cardinality of the set of values of the parameter q is called the number of states. The significant interpretation of the automaton function f  (x1 , x2 , . . . , xn ) = (y1 , y2 , . . . , ym ) is the functioning of the technical device F shown in Fig. 2. Here the input arrows are labeled by the letters xi , i = 1, . . . , n, and the output ones, by the letters yj , j = 1, 2, . . . , m. It is assumed that F functions at discrete moments of time t = 1, 2, . . . . At these moments, every input xi and output yi can take values from El ; the device itself may be in states that are coded by the values from Q; these states are also called the memory for F . The values of outputs and the state at the moment t + 1 are determined by the collection of values of inputs and by the state of the device F at the moment t according to rules (2). n,m the class of all automaton functions with given parameters n and m from N . Let Denote by Pa,l

n,m Pa,l . Pa,l = n,m≥1

We extend the operations η, τ , Δ, and ∇ to Pa,l , and also introduce some other operations. Let f  (x1 , x2 , . . . , xn ) = (y1 , . . . , yj , . . . , ym ). Then (πj f  )(x1 , x2 , . . . , xn ) = fj (x1 , x2 , . . . , xn ), where fj (x1 , x2 , . . . , xn ) coincides with the value yj in f  (x1 , x2 , . . . , xn ). Let f  (xn+1 , xn+2 , . . . , xn+v ) = (ym+1 , . . . , ym+w ). Then (f  σ f  )(x1 , x2 , . . . , xn , xn+1 , xn+2 , . . . , xn+v )   = f  (x1 , x2 , . . . , xn ), f  (xn+1 , xn+2 , . . . , xn+v ) = (y1 , y2 , . . . , ym , ym+1 , ym+2 , . . . , ym+w ). Let u be such that m + 1 ≤ u ≤ m + u. Then    f ∗u f  (x2 , x3 , . . . , xn , xn+1 , xn+2 , . . . , xn+v = (z1 , z2 , . . . , zm+w−1 ), where zj = fj ∗ fu for j = 1, 2, . . . , m and zj  = fj (xn+1 , xn+2 , . . . , xn+v ) for j  = m + 2, m + 3, . . . , m + t. The operations π and σ are called, respectively, projection and union, and the operation of the form ∗u is the extension of the operation ∗s from one-dimensional functions to vector functions and, as before, is called substitution. In total, the operations η, τ , Δ, ∇, π, σ, and ∗u are called operations of extended superposition and are denoted by Σes . Let us introduce one more operation on automaton functions, which is called feedback and denoted by F . We say that an automaton function f  is of type i − j if for f  there is a system of type (2) such that the function ψj (q, e1 , e2 , . . . , en ) fictitiously depends on ei . Let f  be such an automaton function. We 446

consider a function of the form (Fji f  )(x1 , x2 , . . . , xi−1 , xi+1 , . . . , xn ) = (y1 , y2 , . . . , yj−1 , yj+1 , . . . , ym ), which is determined in the following way. Let words of the form ξl = el (1)el (2) . . . el (r), where l = 1, 2, . . . , i − 1, i + 1, . . . , n, be given. Then with the help of (2), using the collection   el (1), e2 (1), . . . , ei−1 (1), ei+1 (1), . . . , en (1) bj (1) for ei (1); after that it is possible it is possible to calculate the value   bj (1).  Now in (2) we substitute to calculate the collections q(2) and b1 (1), b2 (1), . . . , bm (1) . Then it is also possible to calculate the value bj (2) using the collection   e1 (2), e2 (2), . . . , ei−1 (2), ei+1 (2), . . . , en (2) .   (2) for b (2) in (2) makes it possible to calculate the collections q(3) and Again, the substitution of e i j   b1 (2), b2 (2), . . . , bm (2) and so on. Now we assume that    , ζi+2 , . . . , ζm ), (Fji f  )(ζ1 , ζ2 , . . . , ζi−1 , ζi+1 , . . . , ζn ) = (ζ1 , ζ2 , . . . , ζi−1

where ζl = bl (1)bl (2) . . . bl (r) and l = 1, 2, . . . , j − 1, j + 1, . . . , m. Suppose that Ωes,F = Ωes ∪ {F }. The class of operations Ωes,F is called composition. We say that an automaton function f  from Pa,l is a finite automaton function if the alphabet Q in n,m the class of all finite automaton functions system (2) determining this function is finite. Denote by Pa,l,k with parameters n and m. Suppose that

n,m Pa,l,k . Pa,l,k = n,m≥1

We say that an automaton function is true if the alphabet Q in system (2) determining this function n,m n,m and Pa,l,k,t the classes of all true automaton functions and of is a one-element set. We denote by Pa,l,t true finite automaton functions, respectively, with parameters n and m. Suppose that

n,m n,m Pa,l,t , Pa,l,k,t = Pa,l,k,t . Pa,l,t = n,m≥1

n,m≥1

From the content point of view, true automaton functions are interpreted as the functioning of a device F without memory, on the one hand, and on the other hand, they can be considered to be realizations of the functions from Pl with regard to time t that runs the values 1, 2, . . . , and in each moment of time the dependence of the value of the function on the values of the variables is the same. Thus, a Post functional system (Pl , Ωs ) actually leads to Pa,l,t = (Pa,l,t , Ωes ) if we extend the object Pl to the set of vector functions of l-valued logic and extend the operations to Ωes . We also note that a function with delay is interpreted as the functioning of a device F with n inputs and one output whose value b(t) for some τ from N0 and f (x1 , x2 , . . . , xn ) from Pl is determined at any moment t ≥ τ + 1 by the relation b(t) = f a1 (t − τ ), a2 (t − τ ), . . . , an (t − τ ) that, evidently, can be described by a system of the form (2). Let M ⊆ Pa,l . Then for JΩes (M ) = M , the functional system M = (M, Ωes ), and for JΩes,F (M ) = M , the functional system M = (M, Ωes,F ) are called iterative Post functional systems of automaton functions. Examples of such functional systems are functional systems of the form Pa,l,t . For a given l ∈ N1 , the main Post functional system of automaton functions is Pa,l,k = (Pa,l,k , Ωes ),

Pa,l = (Pa,l , Ωes ),

∗ Pa,l,k = (Pa,l,k , Ωes,F ),

∗ Pa,l = (Pa,l , Ωes,F ).

(3)

Let us give the main results concerning our problems for Post functional systems of automaton functions. 447

Theorem 5.1 (see [15]). For any l from N1 among the main Post functional systems of automaton ∗ is finitely generated. functions only the functional system Pa,l,k ∗ , there exists a countable set of bases Theorem 5.2 (see [14]). For any l from N and m from N1 in Pa,l,k of power m.

An automaton function forming a complete system in M is called a Sheffer function. Further simplification of the basis is achieved by minimization of the number of variables, dimensionality, and the number of states of a Sheffer automaton function. The next assertion gives the final answer concerning the form of the simplest in this sense Sheffer automaton functions. ∗ , there exist Sheffer one-dimensional automaton Theorem 5.3 (see [26]). For every l from N1 in Pa,l,k functions of two variables and with two states.

For the other two main Post functional systems of automaton functions, the following assertion gives the answer to the basis problem. ∗ , there are no bases; in P Theorem 5.4 (see [15]). For any l from N1 in Pa,l and Pa,l a,l,k there is a countable basis as well as a complete system containing no basis.

As far as to the completeness problem, the situation is described by the following assertions. Theorem 5.5 (see [5, 15]). For the main Post functional system of automaton functions the set Σπ (M) ∗ for any l from N1 . forms a c-system only for M = Pa,l,k Theorem 5.6 (see [14]). For any l from N1 , the set Σπ (M) has cardinality of continuum for M ∈ ∗ } and hypercontinuum for M ∈ {P , P ∗ }. {Pa,l,k , Pa,l,k a,l a,l As a corollary we obtain that the corresponding lattices of closed classes in the main Post functional system of automaton functions have the cardinalities mentioned in Theorem 5.6. ∗ ) is called c-criterial if any finite set M ⊆ P A system Σ ⊆ Σ(Pa,l,k a,l,k is complete if and only if for  any set K ∈ Σ the condition M ⊆ K is valid. ∗ ∗ ) for Theorem 5.7 (see [14]). In Pa,l,k there exist countable c-criterial systems of the form Σ ⊆ Σπ (Pa,l,k any l from N1 .

It should be pointed out that in the general case assigning automaton functions from Pa,l is not efficient; therefore, the problem of expressibility and completeness can be posed only for effectively assigned systems. Theorem 5.8 (see [11]). The problem of expressibility for effectively assigned finite systems of automaton functions in the main Post functional system of automaton functions and the problem of completeness in Pa,l are not algorithmically decidable for any l from N1 . Thus, the extension of the functional possibilities of automaton functions in comparison to the functions of l-valued logic and functions with delays considerably complicates the solution of the problems we are interested in for algebraic automaton functions. The study of the nature of this complexity was carried out in different directions. Here we dwell on the problem of approximate completeness and on the problem of completeness of specially enriched systems of automaton functions. The first of these problems has two modifications, the problem of τ -completeness, τ ∈ N , and the problem of approximate completeness (A-completeness); the next section is devoted to this problem. We call attention to special functional systems P1 , P2 , P3 , and P4 that are subalgebras of the corresponding main Post functional system of automaton functions from (3). Each of them consists of all one-place and one-dimensional automaton functions from the main Post functional system, and operations employed in them are the same as in the corresponding Post functional system of automaton functions, except for 448

the operations σ and π. As has been established in [2, 15], they have no bases. Moreover, P1 contains a subalgebra P1 of all one-to-one mappings, which is a group with the operation of substitution and which models by one of its parts a group of Burnside type [1], i.e., a finitely generated group in which the orders of the elements are finite but are not bounded in totality. Still open are the questions of the existence of bases in P1 as well as the problem of algorithmic decidability of the property of finiteness of the order of its elements and expressibility of these elements by other elements. In conclusion, we note that Theorems 5.1, 5.2, 5.5, and 5.6 and the facts mentioned here concerning one-place algebras remain valid also for the case of extending the value l to countable in the functional system of functions, which in this way generalizes automaton functions. 6. Conditions of τ - and A-Completeness for Automaton Functions Automaton functions f and g are τ -equivalent if they coincide on all input words of length τ (in this case we write f τ g) and are A-equivalent if f τ g for any τ from N . On the set B(Pa,l ) we introduce a relation Δτ such that M Δτ M  for M, M  ⊆ Pa,l if for every function f from M there exists g from M  such that f τ g. It is clear that this relation forms a preorder and, consequently, can be represented as a relation of a partial order on classes of equivalence including all such elements M and M  for which the relations M Δτ M  and M  Δτ M are valid; in this case we write M τ M  and the elements themselves are called τ -equivalent. On B(Pa,l ) we introduce one more relation, assuming that for M, M  ⊆ Pa,l the relation M ΔA M  is fulfilled if M τ M  for any τ from N . This relation is also a preorder for representatives M and M  of its class of equivalence, and when M ΔA M  and M  ΔA M we write M A M  and the representatives themselves are called A-equivalent. Theorem 6.1 (see [8]). For any M ⊆ Pa,l and τ ∈ N , JΩes (M ) τ JΩes,F (M ),

JΩes (M ) A JΩes,F (M ).

Thus, the actions of the operators JΩes (M ) and JΩes,F (M ) coincide up to τ - and A-equivalence, and thereby in this sense the operation of feedback F turns out to be modeled by operations of extended superpositions, which we are going to use further on. Let M, M  ⊆ Pa,l . We say that M is τ -expressible by M  if M Δr JΩes (M  ), and A-expressible by M  if M ΔA JΩes (M  ). Theorem 6.2. For effectively assigned finite sets M, M  ⊆ Pa,l , the relation M Δr JΩes (M  ) is algorithmically decidable for any τ from N . Theorem 6.3 (see [7]). For finite sets M, M  ⊆ Pa,l,k , the relation M ΔA JΩes (M  ) is algorithmically undecidable. Let M ⊆ PA,l and M A JΩes (M  ). The set M  ⊆ M is called τ -complete in M if JΩes (M  ) τ M and A-complete if JΩes (M  ) A M . Theorem 6.4. If M ⊆ Pa,l , M A JΩes (M ), M is decidable, there is a finite A-complete subset of M , and τ ∈ N , then there exists an algorithm determining for any finite decidable subset M  ⊆ M whether it is τ -complete in M . In fact, this theorem follows from Theorem 2.2. We verify this fact in the following way. Let f ∈ Pa,l and τ ∈ N . Consider the set Elr , assuming that its elements are coded by words of length τ in the alphabet El . Then, examining the function f from Pa,l only on words of length τ , we can consider it to belong to Plr . Thus, from examining automaton functions we passed to functions of lτ -valued logic. It remains to note that the operations of extended superposition with respect to expressibility and completeness are actually reduced to the operations of superposition. The following assertion is a corollary of Theorem 6.1 and the relation Pa,l,k A Pa,l . 449

Theorem 6.5. The conditions of τ -completeness and A-completeness coincide for all main Post functional systems of automaton functions. We point out an essential difference between the notions of τ -completeness and A-completeness which is given in the following assertion. Theorem 6.6. In each of the main Post functional systems of automaton functions there exist finite A-complete systems and countable A-complete systems containing no finite A-complete subsystems. The difference in the notions of τ -completeness and A-completeness appears in the following assertion. Theorem 6.7 (see [7]). If M ⊆ Pa,l,k and M is finite, then there is no algorithm establishing whether M is A-complete in Pa,l,k . At the same time, there is some similarity in the notions of τ - and A-completeness and it reveals itself in the approach to solving problems of τ - and A-completeness in terms of precomplete classes. If M ⊆ Pa,l , M A JΩes (M ), and M  ⊆ M , then M  is called τ -precomplete in M if it is not τ -complete in M , but for any function f from M \ M  the set M  ∪ {f } is τ -complete in M . The notion of an A-precomplete is introduced analogously. Let Σπ,τ (M ) and Σπ,A (M ) be the sets of all τ -precomplete and A-precomplete sets in M , respectively.  Σπ,τ (M ). Theorem 6.8. If M ⊆ Pa,l and M A JΩes (M ), then Σπ,A (M ) = τ ≥1

Theorem 6.9. If λ ∈ {r, A}, r ∈ N , M ⊆ Pa,l , M A JΩes (M ) in M there is a finite λ-complete subset, and M  ⊆ M , then M  is λ-complete in M if and only if M   K for any K ∈ Σπ,λ M . This assertion with regard to Theorems 6.5 and 6.8 reduces the solution of τ - and A-completeness problems in the main Post functional system of automaton functions to the description of the set Σπ,τ Pa,l (this fact was obtained in [8]). Let us give this description. Let t ∈ N . Denote by Elt the set of all words  = e(1)e(2) . . . e(t) of length t in the alphabet El . For h ∈ N and T = (t1 , t2 , . . . , th ), where ti ∈ N , i = 1, . . . , h, we put ElT = Elt1 × Elt2 × · · · × Elth , T ∈ N h . Let ρ(y1 , y2 , . . . , yh ) be an h-ary predicate whose arguments yi take values from Elti , i = 1, . . . , h. As previously, let ρ1 and ρ0 be, respectively, the sets of true and false collections of values of the variables for ρ. We say that a function f (x1 , x2 , . . . , xn ) from Pa,l preserves ρ if from the truth of each element of the row ρ(α11 , α21 , . . . , αh1 ), ρ(α12 , α22 , . . . , αh2 ), . . . , ρ(α1n , α2n , . . . , αhn ) follows the truth of the expression   ρ f (α11 , α12 , . . . , α1n ), f (α21 , α22 , . . . , α2n ), . . . , f (αh1 , αh2 , . . . , αhn ) . We denote the class of all such functions by Ua (ρ). We introduce the function ν : El∗ × El∗ → N0 , putting for 1 = Elt1 , 2 = Elt2 , and t = min(t1 , t2 ) ⎧ 0 if e1 (1) = e2 (1), . . . , e1 (t) = e2 (t), ⎪ ⎪ ⎪ ⎨i if 1 ≤ i ≤ t − 1 and ε (1) = ε (1), . . . , 1 2 ν(ε1 , ε2 ) = ⎪ ε1 (t − i) = ε2 (t − i), but e1 (t − i + 1) = e2 (t − i + 1), ⎪ ⎪ ⎩ t if ε1 (1) = ε2 (2). We determine the relation of preorder ≤ on the set ElT . Let A = (α1 , α2 , . . . , αh ) and A = (α1 , α2 , . . . , αh ) be elements from ElT . We write A ≤ A if ν(αi , αj ) ≤ ν(αi , αj ) for any i, j ∈ N1h . Let t = max{t1 , t2 , . . . , th }, h ≤ lr , and t ≥ 2. If l = 2, then we put h = 2. Let, in A for h ≥ 2, us have ν(αi , αj ) = 0, i = j. The set of all A such that A ≤ A is called the ν-set determined by the element A. We denote this set by ξ. Such ξ is divided into two subsets: ξ (m) consisting of all maximal 450

elements with respect to the relation ≤ and ξ (m) including the rest of the elements from ξ. Thus, for h = 1 we have ξ (m) = ∅. It is clear that the value ν = (αi , αj ) does not depend on the choice of A from ξ (m) ; therefore instead of ν = (αi , αj ) we write ν = (i, j). For l ≥ 2 and t ≥ 1 we indicate seven families of predicates. Let h ≥ 1, T = (t1 , t2 , . . . , th ), and ξ ⊆ ElT . A substitution γ of the numbers 1, 2, . . . , h is called a ξ-substitution if (αγ(1) , αγ(2) , . . . , αγ(h) ) ∈ ξ for any (α1 , α2 , . . . , αh ) from ξ. Let s ≥ 1. We say that the set {(α11 , α21 , . . . , αh1 ), (α12 , α22 , . . . , αh2 ), . . . , (α1s , α2s , . . . , αhs )} of elements T from if there exists a collection of ξ-substitutions γ1 , γ2 , . . . , γs such that ν(i, j) ≤  q El isp ξ-consistent  ν αγq (i), αγp (j) for any q and p from N1s , and any i and j from N1h . Let ρ(y1 , y2 , . . . , yh ) be a predicate for which ρ1 ⊆ ξ. We say that ρ is ξ-reflexive if ξ (m) ∈ ρ1 , and ξ-symmetrical if (αγ(1) , αγ(2) , . . . , αγ(h) ) ∈ ρ1 for any (α1 , α2 , . . . , αh ) from ρ1 and any ξ-substitution γ. A ξ-reflexive and ξ-symmetrical predicate ρ is called ξ-elementary if the set ξ \ ρ1 is ξ-consistent. For such ρ, A ∈ ξ \ ρ1 , and i ∈ N1h we determine subsets Cρi (A), Qiρ (A), and iρ (A) of the set El in the following way: • a ∈ Cρi (A) if and only if there exists αi ∈ Elti such that ν(αi , αi ) ≤ 1, αi (ti ) = a, and any element (α1 , α2 , . . . , αh ) from ξ is contained in ρ1 ; • b ∈ Qiρ (A) if and only if in ξ \ ρ1 there exists an element (α1 , α2 , . . . , αi−1 , αi , . . . , αh ) such that ν(αi , αi ) ≤ 1, αi (ti ) = b; • the set iρ (A) coincides with Cρi (A) if Cρi (A) = ∅, and with Qiρ (A) otherwise. Let n ≥ 1 and let R = {ρ1 , ρ2 , . . . , ρn } be an arbitrary system of ξ-elementary predicates. We say that R is T -consistent if Qiρ (A) = El for any σ ∈ N1n , i ∈ N1h , and A ∈ ξ \ ρσ1 . We say that R is W -consistent if for all σ, σ ∈ N1n , i ∈ N1h , A ∈ ξ \ ρσ1 , A ∈ ξ \ ρσ1 the sets Cρi σ (A) and Cρi σ (A ) are simultaneously either empty or not empty, and also if Cρi σ (A) = ∅, then for any b ∈ El there exists j ∈ N1h such that tj = ti , ν(i, j) ≤ 1, b ∈ Qjρσ (A). Let n ≥ 1, σi ∈ N1q , Ai = (α1i , α2i , . . . , αni ), Ai ∈ ξ \ ρσ1 i , and ji ∈ N1h for i ∈ N1n . Then if σi = σi for n  jρlσi (Ai ) = ∅, then i = i and tji = tji and ν(αj11 , αj2i ) ≤ 1 for all i, i ∈ N1q and i ∈ N1n \ {1}, and i=1 1 the system R is called Q-consistent.  Let n ≥ 2, i ∈ N1n , σj ∈ N1q , and Ai ∈ ξ \ ρσ1 i . We assume that ν(α1j , α1j ) = 1 for all j, j  ∈ N1n , j = j  . n  i ρjσj (Aj ) = ∅. We suppose that Let tij = tij  and for all ij , ij  ∈ N1h , ν(αi11 , αij ) ≤ 1 for j > 1, and j=1

under these conditions there exists lν ∈ N1n , ν ∈ N1q , such that ilν ∈ N12 , the sets Alν are ξ-consistent, q  i and ρlσνlν (Alν ) = ∅. Then we say that the system R is D-consistent. ν=1

The family of predicates Zl (r). This family is nonempty for l ≥ 2 and r ≥ 1. A predicate ρ belongs to Zl (r) if and only if ρ1 ⊂ ξ, ξ ⊆ ElT , T = (t1 , t2 , . . . , th ), h ≥ 1, max{t1 , t2 , . . . , th } ≤ r, and for some m  m ≥ 1 we have ρ1 = ρi1 , where ρi is a ξ-elementary predicate and the ρi themselves form a T -, W -, i=1

and Q-consistent system, and for any j ∈ N1h and A ∈ ξ \ ρ1 , the set Cρi (A) is nonempty. The family of predicates Jl (r). This family is nonempty for r ≥ 1 and l > 2, and also for r ≥ 2 and l = 2. A predicate ρ belongs to Jl (r) if and only if ρ1 ⊆ ξ ⊆ ElT , T = (t1 , t2 , . . . , th ), h ≥ 3, m  max{t1 , t2 , . . . , th } ≤ r, for some m ≥ 1 we have ρ1 = ρi1 , where ρi is a ξ-elementary predicate and the i=1

ρi themselves form a T -, W -, and Q-consistent system; there are numbers i, j, l ∈ N1h , i = j, i = l, j = l, such that for A from ξ \ ρ11 the set Cρu (A) is empty for u ∈ {i, j, l}. The family of predicates Dl (r). This family is nonempty for r ≥ 1 if l > 2 and for r ≥ 2 if l = 2. A predicate ρ belongs to Jl (r) if and only if ρ1 ⊂ ξ ⊆ ElT , T = (t1 , t2 , . . . , th ), h ≥ 2, max{t1 , t2 , . . . , th } ≤ 451

r, for some m ≥ 1 we have ρ1 =

m  i=1

ρi1 , where ρi is a ξ-elementary predicate and the ρi themselves form

a T -, W -, and Q-consistent system; for any A ∈ ξ \ ρ, the sets Cρ1 (A) and Cρ2 (A) are empty; if h ≥ 3, then Cρi (A) = ∅ for any i from N1h ; if h = 2, then ρ1 ∩ ξ (m) = ∅. Let, further, l ≥ 2, t ≥ 1, T = (t, t), ξt ⊆ ElT , ξt be a ν-subset, and νξt (1, 2) = 1. The family of predicates Ml (r). This family is nonempty for l ≥ 2 and r ≥ 1. A predicate ρ belongs to Ml (r) if and only if ρ1 ⊂ ξt , t ≤ r, and ρ1 coincides with the relation of partial order determined on ElT and having exactly lt−1 minimal and lt−1 maximal elements. The family of predicates Sl (r). This family is nonempty for l ≥ 2 and r ≥ 1. A predicate ρ belongs to Sl (r) if and only if ρ1 ⊂ ξt , t ≤ r, and there is a substitution σρ on Elt decomposing into a product of cycles of equal prime length p ≥ 2 whose graph coincides with ρ1 , i.e., if a ∈ ElT , then (a, σρ (a)) ∈ ρ1 , and if (a1 , a2 ) ∈ ρ1 , then a2 = σρ (a1 ). ˜ t , t ≥ 1, be the class of all mappings φ of the set E T into the set of substitutions on El . The Let Φ l ˜ t and let Φt consist of all φ such that φa = φa for v(a, a ) ≤ 1. value φ at a is denoted by φa . Let Φt ⊆ Φ Let h ∈ {3, 4}, Th = {t, t, . . . , t}, Kth ⊆ ElTh , and Kth consist of all elements (a1 , a2 , . . . , ah ) such that v(ai , aj ) ≤ 1 for i, j ∈ N1h . Let l = pm , where p is prime, m ≥ 1, and let G = El , + be an Abelian group each of whose nonzero elements has a prime order p. For p = 2, let lp ∈ N1p−1 and 2lp = 1 (mod p). The family of predicates Ll (r). This family is nonempty only for l = pm , where p is prime, m ≥ 1, t ≤ r. A predicate ρ belongs to Ll (r) if and only if for some φ from Φt , t ≤ r, the following assertions are true:   (1) let k = pm , p > 2; then ρ1 ⊂ Kt3 and (a1 , a2 , a3 ) from Kt3 belongs to ρ1 if and only if φa1 a3 (t) =     lp φa1 a1 (t) + φa1 a2 (t) ;   4 belongs to ρ if and only if φ (2) let k = pm ; then ρ1 ⊂Kth and a (a , a , a , a ) from K (t) + 1 2 3 4 1 a 1 t 1   φa1 a2 (t) = φa1 a3 (t) + φa1 a4 (t) . We note that the families indicated for r = 1 coincide with the known families for Pl , from Sec. 2. Let t > 2, T = (t, t) and let ξ˜t be a μ-subset ElT such that μξ˜t (1, 1) = 2. The family of predicates Vl (r). This family is nonempty for l ≥ 2 and r ≥ 2. A predicate ρ belongs (m) to Vl (r) if and only if ρ1 ⊂ ξ˜t , t ≤ r, and (a1, a2) ∈ ξ˜t ∩ ρ1 if and only if a1 (t) = a2 (t); there is φ (m) from Φt such that the inclusion (a1 , a2 ) ∈ ξ˜t ∩ ρ1 is equivalent to the existence of α from El such that a1 (t) = φa1 (α) and a2 (t) = φa2 (t). Let Wl (r) = Zl (r) ∪ Jl (r) ∪ Dl (r) ∪ Ml (r) ∪ Sl (r) ∪ Ll (r) ∪ Vl (r)   and let U Wl (r) be the set of classes of automaton functions preserving predicates from Wl (r).   Theorem 6.10 (see [8]). The equality Σπ,r (Pa,l ) = U Wl (r) is true. 7. Conditions of Completeness for Special Systems of Automaton Functions Another way of studying the completeness properties of automaton function systems consists of enriching the operations performed both on automaton functions and on automaton function systems which are tested for completeness. We consider the second situation. Here two approaches are of interest. The first approach consists of considering the Slupecki problem for the functional system Pa,l,k and the ∗ that contain some closed class of second one concerns such systems of automaton functions from Pa,l,k truth automaton functions. Following [25], a finite system T of finite automaton functions in Pa,l,k is 1,1 called a Slupecki system if JΩes (Pa,l,k ∪ T ) = Pa,l,k . Theorem 7.1 (see [4]). For any l from N1 , there exist Slupecki systems of finite automaton functions from Pa,l,k . 452

A precomplete class of the main Post system of automaton functions is called a Slupecki class if it contains all homogeneous functions from the carrier of the Post system of automaton functions. Theorem 7.2. The cardinality of the set of Slupecki classes is equal to continuum in the functional ∗ ∗ , for any l and is equal to hypercontinuum in the functional systems Pa,l and Pa,l systems Pa,l,k and Pa,l,k from N1 . Note that the hypercontinuum property in this theorem remains valid also for functional systems of functions which are obtained from automaton functions by extending the value of the parameter l to countable. The second approach was first realized in the form of the following assertion. Theorem 7.3 (see [3]). For any l from N1 , there exists an algorithm which establishes for any finite set ∗ . M ⊆ Pa,l,k whether the set M ∪ Pa,l,k,t is complete in Pa,l,k Later on this approach was developed for l = 2 in the following way. Let Q be a closed Post class of Boolean functions. We interpret these functions as truth finite automaton functions. Denote by KQ the class of all finite sets M of finite automaton functions from Pa,2,k such that M ⊇ Q. Our prime interest here is the existence of an algorithm which establishes for any M from KQ whether the set is complete in ∗ (to be more exact, for which Q this algorithm exists). It is clear that if such an algorithm exists for Pa,2,k some Q, then it also exists for any Post class Q such that Q ⊇ Q. On the contrary, if such an algorithm does not exist, then it does not exist for any Post class Q ⊆ Q. Thus, the separation of algorithmically decidable cases from algorithmically undecidable ones is achieved by indicating such a family Φ of the Post class Q for which the completeness property is not algorithmically decidable, but for any Post class such that Q ⊃ Q it is decidable. Theorem 7.4 (see [6]). The family Φ is equal to {F1∞ , F2∞ , F3∞ , F4∞ , F5∞ , F6∞ , F7∞ , F8∞ , L2 , L3 , L5 , S6 , P6 , O9 }. A special case of this assertion is Theorem 7.3 for l = 2. As is shown in [6], the assertion of Theorem 7.4 holds also for the case of A-completeness with the proper interpretation of the set Φ. 8. Linear Automaton Functions An automaton function from Pa,l,k is linear if in its system (1) the vector-functions φ and ψ are linear modulo l with respect to their variables. Denote by La,l,k the class of all linear automaton functions. It is not difficult to see that IΩes,F (La,l,k ) = La,l,k . Let us consider the functional systems La,l,k = (La,l,k , Ωes ) and L∗a,l,k = (La,l,k , Ωes,F ). Theorem 8.1. Among the functional systems La,l,k and L∗a,l,k , only L∗a,l,k is finitely generated. A solution of the completeness problem for L∗a,l,k is obtained for l = 2, and we present it [9] using the notation La instead of La,l,k and the notation La instead of La,l,k . Let Γa , a ∈ E2 , be the class of all linear automaton functions f (x1 , x2 , . . . , xn ) = (y1 , y2 , . . . , ym ) such that f (a, a, . . . , a) = (a, a, . . . , a). We say that a linear automaton function f (x1 , x2 , . . . , xn ) depends on xi with a shift if, in its system (1), xi is absent in the equations for ψ; otherwise xi is called an immediate variable. Let V1 be the class of all linear automaton functions having no more than one immediate variable. Let V2 be the class of all linear automaton functions having an odd number of immediate variables. Denote by RC the class of all linear automaton functions having exactly one essential variable and by RH the class of all linear automaton functions with exactly one immediate variable. The class of all linear automaton functions without immediate variables is denoted by C. Let αs [0] be the word of length s of the form 00 . . . 0. Denote by L0 the class of all linear automaton functions f (x1 , x2 , . . . , xn ) such that f (αs [0], αs [0], . . . , αs [0]) = (αs [0], αs [0], . . . , αs [0]) for any s from N . 453

Let L1 be the class of all linear automaton functions of one variable and L01 = L0 ∩ L1 . Denote by E2 [z] the ring of polynomials in z over the field E2 with the usual operations of addition and multiplication of polynomials. For {u, v, u , v  } ⊂ E2 [z] we consider the fractions u/v, u /v  which we assume equal if uu1 = u u2 and vu1 = v  u2 for some u1 and u2 from E2 [z] \ {0}. The degree of a polynomial u is denoted by deg u. Let Q2 (z) be the set of all fractions u/v, where v ∈ E2 [z] \ {0} and if u/v is incontractible, then v is not divided by z. It is possible to show that L01 and Q2 (z) are isomorphic (notation: ∼) and retain the operations of addition and multiplication; therefore they are identical in a sense. Let u/v ∈ Q2 (z), f ∈ La , and u/v ∼ f . We say that f possesses the O-property if either u/v ∈ RH and deg u = deg v or u/v ∈ / RH and deg u < deg v. We consider polynomials pi from Q2 (z) ordered according to ascending degree, i.e., deg pi ≤ deg pi+i for i ∈ N , and let p1 = ξ. If u + v or u is divided by ξpi , then we say that f possesses the i-property. If deg u < deg v, then f possesses the O -property; if deg u ≤ deg v, then f possesses the O -property. If u is divided by pi , then f possesses the i -property; if v (1) is not divided by pi , then it possesses the i -property. Let Mi consist of all linear automaton functions f (1) having the i-property, i ∈ N0 , and let Ri consist of all linear automaton functions f with the i -property. For a linear automaton function f (x1 , x2 , . . . , xn ), there exist functions f1 (x1 ), f2 (x2 ), . . . , fn (xn ) from L1 and γ from C such that f (x1 , x2 , . . . , xn ) =

n 

fi (xi ) + γ

(mod 2).

i=1

Denote the set of functions f1 , f2 , . . . , fn by μ(f ). Let Mi consist of all linear automaton functions f such (1) that μ(f ) ⊂ Mi . For a linear automaton function f , let the following property be fulfilled: if xj is the only essential variable, then fj from μ(f ) possesses the i -property; and if the indicated property is absent in xj , then fj possesses the i -property. The class of all such f is denoted by RjC . For a linear automaton function f , let the following property be fulfilled: if xj is the only immediate variable, then fj from μ(f ) possesses the i -property; otherwise fj possesses the i -property. The class of such f is denoted by RjH . Denote by J the family consisting of all classes Γ0 , Γ1 , V1 , V2 , Mi , RjC , and RjH for i ∈ N1 , j ∈ N . Theorem 8.2 (see [9]). The relation Σπ (L∗a ) = J holds. Thus, in the functional system L∗a there is only a countable set of precomplete classes and by virtue of the fact that L∗a is finitely generated they form a criterial system. By analogy with the case of the functions with delays the following assertion holds. Theorem 8.3 (see [9]). There is an algorithm establishing for any finite system of linear automaton functions from L∗a whether it is complete. Acknowledgments. This work was partially supported by the Russian Foundation for Basic Research (project No. 06-01-00240).

REFERENCES 1. S. V. Aleshin, “Finite automata and the Burnside problem for torsion groups,” Mat. Zametki, 29, 319–328 (1972). 2. S. V. Aleshin, “On the absence of bases in some classes of initial automata,” Problemi Kibernet., 22, 67–75 (1970). 3. D. N. Babin, “A decidable case of the completeness problem for automata functions,” Diskret. Mat., 4, No. 4, 41–55 (1992). 454

4. D. N. Babin, “On completeness of the binary boundedly determined functions with respect to superposition,” Diskret. Mat., 1, 423–431 (1991). 5. D. N. Babin, “On superpositions of bounded-determined functions,” Mat. Zametki, 47, 3–10 (1990). 6. D. N. Babin, “Undecidability of the completeness and A-completeness problems for some systems of automaton functions,” Diskret. Mat., 5, 31–42 (1995). 7. V. A. Buyevich, “On algorithmic unsolvability of A-completeness recognition for bounded-determined functions,” Mat. Zametki, 29, 687–697 (1972). 8. V. A. Buyevich, “On τ -completeness in the class of determined functions,” Dokl. Akad. Nauk SSSR, 326, 399–404 (1992). 9. A. A. Chasovskikh, “On completeness in the linear automata class,” Mat. Problemi Kibernet., No. 3, 140–166 (1995). 10. P. Cohn, Universal Algebra, Wiley, New York (1965). 11. M. I. Kratko, “Algorithmic undecidability of the completeness recognition problem for finite automata,” Dokl. Akad. Nauk SSSR, 155, 35–37 (1964). 12. V. B. Kudryavtsev, “A completeness theorem for one class of automata without feedback,” Probl. Kibernet., 8, 91–115 (1962). 13. V. B. Kudryavtsev, Functional Systems [in Russian], Izd. Mosk. Univ., Moscow (1982). 14. V. B. Kudryavtsev, “On the cardinality of the sets of precomplete sets of some functional systems connected with automata,” Probl. Kibernet., 13, 45–74 (1965). 15. V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, An Introduction to Automata Theory [in Russian], Nauka, Moscow (1985). 16. Lo Chzhu-Kai, “Precomplete classes determined by the k-nary relations in k-valued logic,” Acta Sci. Natur. Univ. Jilin., No. 3 (1964). 17. Lo Chzhu-Kai and Lu Sui-Khua, “Precomplete classes determined by the binary relations in many-valued logic,” Acta Sci. Natur. Univ. Jilin., No. 4 (1964). 18. A. I. Maltsev, “Iterative algebras and the Post diversity,” Algebra Logika, 5, No. 2, 5–24 (1966). 19. V. V. Martynyuk, “An investigation of some classes of functions in many-valued logic,” Probl. Kibernet., 3, 49–60 (1960). 20. J. McCarthy and C. Shannon, eds., Automata Studies, Princeton Univ. Press, Princeton (1956). 21. Pan Yun-Tse, “A method of discovering all precomplete classes in many-valued logic,” Acta Sci. Natur. Univ. Jilin., No. 2 (1964). 22. E. Post, Two-Valued Iterative Systems of Mathematical Logic, Princeton Univ. Press, Princeton (1941). 23. I. Rosenberg and T. Hikata, “Completeness for uniformly delayed circuits,” in: Proc. 13th Int. Symp. on Multiple-Valued Logic. Kyoto, Japan, 1983, pp. 1–9. 24. I. G. Rosenberg, “La structure des functions de plusiers variables sur un ensemble fini,” C. R. Acad. Sci. Paris, 260, 3817–3819 (1965). 25. J. Slupecki, “Kriterium pelnosci wielowar tosciowych systemow logiki zdan,” C. R. S´eances Soc. Sc. Lettr. Varsovie., Cl. III, 32, 102–128 (1939). 26. E. V. Vetrennikova, “A simple example of the universal b. d. function,” in: Discrete Analysis [in Russian], Inst. Mat. SO AN SSSR, Novosibirsk (1983), pp. 5–11. 27. S. V. Yablonskii, “Functional constructions in the k-valued logic,” Tr. Mat. Inst. Steklova, 51, 5–142 (1958). 28. S. V. Yablonskii, O. P. Gavrilov, and V. B. Kudryavtsev, Boolean Functions and Post Classes [in Russian], Nauka, Moscow, 1966. 29. Yu. I. Yanov and A. A. Muchnik, “On the existence of k-valued closed classes that do not have a basis,” Dokl. Akad. Nauk SSSR, 127, 144–146 (1959). 30. E. Yu. Zakharova, “Completeness criteria of a system of functions from Pk ,” Probl. Kibern., 18, 5–10 (1967).

455

31. E. Yu. Zakharova, V. B. Kudryavtsev, and S. V. Yablonskii, “On precomplete classes in k-valued logics,” Dokl. Akad. Nauk SSSR, 186, 509–512 (1969). V. B. Kudryavtsev Moscow State University, Moscow, Russia E-mail: [email protected]

456