Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

216 V. B. Kudryavtsev

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 ﬁnally we consider ﬁnite

automata, i.e., automata functions of the 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 books which contain them [24, 30] 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 this approach is the concept of a precomplete class. For ﬁnitely-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 to be ﬁnite, and from their characterization

follows the algorithmic solvability of the completeness problem. Proceeding in this direction

and describing explicitly all precomplete classes S. V. Yablonskii solved the completeness

problem for functions of three-valued logic, and, together with A. V. Kuznetsov, found certain

families of precomplete classes for an arbitrary ﬁnite-valued logic. Then by the eﬀorts of

many researchers new families of this kind were discovered in succession, and the conclusive

constructions were obtained by Rosenberg [26]. A summary of these constructions is also

given here.

For automata with limited memory, solutions of completeness and expressibility problems

are given as well as problems of weak versions of these assertions. By an automaton of this

kind is meant a pair (f,t), where f is a function of k-valued logic and t is its calculation

time. 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. From this description an algorithm deciding the completeness of ﬁnite

automata systems is deduced [9].

The transition to the general case of automata aﬀords us an opportunity to discover the

continuum set of precomplete classes [17] and the algorithmic undecidability of the complete-

ness problem [15]. Therefore it is of current importance to ﬁnd ways of both weakening the

completeness properties and, conversely, of enriching this notion.

The ﬁrst direction is realized by considering problems of r-completeness and A-complete-

ness, which consist, respectively, in checking the possibility of generating all mappings on

words of length r and also such mappings for any ﬁxed r. The main results here are an

explicit description of all r-andA-precomplete classes and the algorithmic undecidability of

the A-completeness problem [8].

On the automata functional systems 217

Another realization in this direction is considering automata with Baire metrics with

the given precision ε [23]. The problem of ε-completeness also turned out to be undecid-

able, though there exists a constructive automata kernel (consisting of strongly connected

automata) with ε-completeness property.

There exists a dual view to the sequential view of automata—the acceptor view proposed

by Kleene. In this case automata are factored by the property of representing identical events.

The completeness property in this case is called Kleene-completeness. This problem is also

undecidable [13].

We can also consider Kleene algebra over regular events. In this case the completeness

problem is still undecidable, yet there exist interesting subalgebras for which completeness is

decidable [14].

The second direction is realized by stratifying all ﬁnite automata systems from the point

of view of completeness and of 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 express-

ibility and completeness, the review also outlines those directions which are insuﬃciently or

poorly developed. Only model cases of automata functional systems are dealt with here. The

general constructions implemented by the author in [18] are not touched upon here.

2 The main notions and problems

Let N = {1, 2,...}, N

= N ∪{0}, N

= N \{1},andforh ∈ N let N

= {1, 2,...,h}.Let

us consider a set M and a mapping ω : M

→ M,whereM

is the n-th Cartesian power of

the set M and n ∈ N .LetP

be the set of all such mappings ω for any n,andQ ⊆ P

We consider the universal algebra (u.a.) M =(M, Ω) where M is called a carrier and Ω

is a class of operations. We associate a sequence of sets

(i)

,i ∈ N, with a subset M ⊆ M

in the following way.

Let

(1)

= M . Then, the set M

(i+1)

consists of all elements m from M for which there

exist ω from Ω and m

,...,m

from M

(i)

such that m = ω(m

,...,m

). We denote

Ω

(M)=

∞



i=1

(i)

It is not diﬃcult to see that I

Ω

is a closure operator on the set B(M) formed by all subsets of

the set M. Thus, for I

Ω

the conditions I

Ω

(M) ⊇ M, I

Ω

(M)) = I

Ω

(M) are always fulﬁlled,

and if

M ⊇ M



,thenI

Ω

(M) ⊇ I

Ω



). The set I

Ω

(M) is called the closure of the set M ,

and

M itself is a generating set for I

Ω

(M). The set M is called closed if M = I

Ω

(M).

Let Σ(M) be the set of all closed subsets in M.Itissaidthat

M is expressible in terms

of M



if M ⊆ I

Ω



). The set M is called complete if I

Ω

(M)=M. A complete set is called

a basis if none of its proper subsets is complete.

The main problems for M which will interest us are those of expressibility and complete-

ness as well as the problems on bases, on the lattice of closed classes, on their modiﬁcation

and some other related questions.

218 V. B. Kudryavtsev

By the problem of expressibility is meant the indication of all pairs

M, M



such that M

is expressible in terms of M



; by the problem of completeness is meant the indication of all

complete subsets; the problem of bases is the description of all bases if they exist; the problem

of the lattice is the construction of the lattice of all closed classes and the determination of

its properties.

The knowledge of the lattice Σ(M) gives the solution of the problems of expressibility and

completeness. Thus, expressibility of

M in terms of M



means veriﬁcation of the condition

Ω

(M) ⊆ I

Ω



). For the solution of the completeness problem the following scheme is used.

AsystemΣ



⊆ Σ(M) is called criterial (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 } = ∅,which

is later assumed, then Σ(M) \{M } = ∅ is a c-system. It is not diﬃcult to see that dual

atoms of the lattice Σ(M), which are also called precomplete classes,belongtoanyc-system.

Let Σ

(M) be the set of all precomplete classes and Σ

(M) be the set of all classes from

Σ(M) which are not a subsets of any precomplete class from Σ

(M). It is not diﬃcult to

verify that the following assertion holds.

2.1 Proposition The set Σ

(M) ∪ Σ

(M) forms a c-system in u.a. M.

Of special interest is the situation where Σ

(M) is the empty set, since in this case the

system Σ

(M)formsac-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

u.a. M is called ﬁnitely-generated if there exists a ﬁnite subset M



⊆ M which is complete.

The following assertion is known [12].

2.2 Proposition If a u.a. M is ﬁnitely-generated, then Σ

(M) forms a c-system.

We note that in the general case the converse is false. Let us now consider the case where

the set M consists of functions. It is the main case for us. In this case the u.a. M is called

a functional system (f.s.).

Let E be a set, and let a function f have the form f : E

→ E,wheren ∈ N.Let

U = {u

,...} be the alphabet of variables with values in E, i ∈ N. Towriteafunction

f, we use the expression f =(u

,...,u

). Denote the class of all such functions by P

In order to avoid complex indices in the variables u

we use metasymbols x, y, z for them,

possibly with indices.

Following Maltsev [20], we introduce in P

unary operations η, τ,&, ∇, which are deﬁned

in the following way:

(ηf)(x

,...,x

)=f(x

,...,x

);

(τf)(x

,...,x

)=f(x

,...,x

);

(∆f)(x

,...,x

n−1

)=f(x

,...,x

n−1

)ifn>1;

(ηf)=(τf)=(∆f )=f if n =1;

(∇f)(x

,...,x

n+1

)=f(x

,...,x

n+1

The form of these operations reﬁnes the operations from [17].

Let us introduce in P

a binary operation ∗ in the following way. For the functions

f(x

,...,x

)andg(x

n+1

n+2

,...,x

n+m

) we assume that

(f ∗ g)(x

,...,x

n+1

n+2

,...,x

n+m

)=(f(g(x

n+1

n+2

,...,x

n+m

),x

,...,x

On the automata functional systems 219

The described operations are called, respectively, shift, transposition, identiﬁcation, extension,

and substitution, and, in total, the operations of superposition. The set of these operations is

indicated by Ω

.LetM ⊆ P

and I

Ω

(M)=M,thenf.s.M =(M, Ω

) is called the Post

iterative f.s.

3 Functions of l-valued logic

The functions from P

are called functions of l-valued logic if

E = E

:= {0, 1, 2,...,l− 1},l≥ 2.

In this case the symbol P

is used instead of P

.Thef.s.P

=(P

, Ω

) is considered to

be one of the main models of the Post iterative f.s. (for brevity’s sake, P.f.s.), the study of

which served as the basis for the formulation of the problems and methods of f.s. theory. If

=(M, Ω

)andM ⊆ P

then M is called P.f.s. of kind l. Let us brieﬂy sum up the

main results in the study of P

which will be important for the consideration of the f.s. of

automaton functions.

Post [24] gave a complete solution of the indicated problems on completeness, expressibil-

ity, bases and closed classes lattice, for P

. Let us describe this lattice preserving his notation.

Consider the set Q of the classes

∞

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; ν =1, 2,...,8;

m =1, 2,....

The functions from P

are called Boolean functions (B.f.). Post denotes the class P

by C

.TheclassC

contains all B.f. f such that f(1, 1,...,1) = 1; C

is the class of all

B.f. such that f(0, 0,...,0) = 0; C

= C

∪ C

. ItissaidthataB.f.f is monotonic if the

inequalities a

≤ b

for all i =1, 2,...,n imply that f (a

,...,a

) ≤ f (b

,...,b

). The class

consists of all monotonic B.f.; A

= C

∩ A

; A

= C

∩ A

; A

= A

∩ A

.Theclass

consists of all B.f. f such that f (x

,...,x

)=f(x

,...,x

)whereB.f.x is called the

negation and

0=1, 1=0;D

= C

∪ D

; D

= A

∪ D

.TheclassL

consists of all B.f.

f(x

,...,x

)=x

+ x

+ ···+ x

+ α (mod 2), α ∈ E

; L

= C

∩ L

; L

= C

∩ L

;

= L

∩ L

; L

= D

∩ L

.TheclassO

consists of all B.f. depending essentially on

no more than one variable; O

= A

∩ O

; O

= D

∩ O

; O

= C

∩ O

; O

= C

∩ O

;

= O

∩ O

; O

= {0, 1}; O

= O

∩ O

; O

= O

∩ O

.TheclassS

consists of all B.f.

of the form x

∨ x

∨···∨x

and of constants; S

= C

∩ S

; S

= C

∩ S

; S

= S

∩ S

The class P

consists of all B.f. of the formal x

∧x

∧···∧x

and constants; P

= C

∩P

;

= C

∩ P

; P

= P

∩ P

. It is said that a B.f. satisfy the condition a

, µ ∈ N

if all µ

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 F

consists of all B.f. with the property a

;

= C

∩ F

; F

= A

∩ F

; F

= F

∩ F

.TheclassF

consists of all B.f. with the

property A

; F

= C

∩F

; F

= A

∩F

; F

= F

∩F

. A B.f. satisﬁes the condition a

∞

if all the collections at which it equals 0 have a common coordinate 0. The property A

∞

introduced by analogy with the change of 0 to 1.

The class F

∞

consists of all B.f. with the property a

∞

; F

∞

= C

∩F

∞

; F

∞

= A

∩F

∞

;

∞

= F

∞

∩ F

∞

.TheclassF

∞

consists of all B.f. with the property A

∞

; F

∞

= C

∩ F

∞

;

∞

= A

∩ F

∞

; F

∞

= F

∞

∩ F

∞

220 V. B. Kudryavtsev

3.1 Theorem [24] For P.f.s. P

the following assertions are true:

(1) The set of all closed classes in P

is countable and coincides with the set Q.

(2) The classes from Q form the inclusion lattice given in Fig. 1.

(3) Every closed class in P

has a basis, and its cardinality is always no more than 4.

(4) The problems of completeness and expressibility for P.f.s. of kind 2 applied to ﬁnite sets

of B.f. are algorithmically decidable.

The properties of P.f.s. of kind l, l>2, turned out to be more complex, which follows

from the assertions given below.

Denote by P

(n)

the set of all functions from P

depending on no more than n variables

,...,u

Figure 1

It is clear that the number of functions in P

(n)

is equal to l

.LetS

be the set of all

functions from P

(n)

each of which is equal to u

for some i, i =1, 2,...,n.IfM ⊆ P

and M

is ﬁnite, then α(M) indicates the greatest number of variables of the functions from M.

On the automata functional systems 221

For a ﬁnitely-generated P.f.s. M of kind l let α(M) be the smallest number α



such that

Ω



)=M and α(M



)=α



for some M



⊆ M . A non-empty set M



⊆ P

α(M)

∩ M is

called an R-set in M if I

Ω



) ∩ P

α(M)

= M



and M



= P

α(M)

, and is denoted by R

α(M)

Let R

α(M)

= R

α(M)

∪ S

α(M)

. We say that a function f (x

,...,x

)fromP

preserves

α(M)

if for any collection of functions g

,...,g

from R

α(M)

f(g

,...,g

) ∈ R

α(M)

The class of all functions from M preserving R

α(M)

is denoted by U(R

α(M)

). An R-set

α(M)

is called maximal if there is no R-set R

α(M)

such that U (R

α(M)

) ⊂ U(R

α(M)

). Let

R(M)bethesetofallmaximalR-sets, and U (R(M)) be the set of all classes of preservation

of elements from R(M). A P.f.s. M is called trivial if M = I

Ω

)orM = I

Ω

({c(x)}),

where c(x)=c, c ∈ E

. The cardinality of a set A is denoted by |A|.

3.2 Theorem [18] If a P.f.s. M =(M, Ω

) of kind l is non-trivial and ﬁnitely-generated,

then:

(1) U(R(M)) = Σ

(M);

(2) |U(R(M))|≤2

α(M)

;

(3) R(M) is constructed eﬀectively.

This theorem is a development of an assertion from [29].

3.3 Corollary The problem of completeness for ﬁnitely generated P.f.s. of kind l is algorith-

mically decidable for any l.

3.4 Theorem [18] The problem of expressibility for ﬁnite sets of ﬁnitely-generated P.f.s.

of kind l is algorithmically decidable for any l.

3.5 Theorem [31] For every l ≥ 3 there exists P.f.s. of kind l such that:

(1) the P.f.s. have a countable basis;

(2) the P.f.s. have a basis of an assigned ﬁnite power;

(3) the P.f.s. have no basis.

3.6 Corollary [31] For every l ≥ 3 the lattice of closed classes in the P.f.s. P

is a contin-

uum set.

As was established in [29], the P.f.s. P

is ﬁnitely generated, therefore Theorems 2 and 3

are valid, and for the set U(R(P

)) its explicit description is found. It is more convenient for

us to present it in a predicate form.

Let ρ(y

,...,y

)beanh-ary predicate, the arguments of which take values from

.Ifρ(a

,...,a

)=a,thenfora = 1 the collection is called true, and for a =0it

is false. The set of all true collections is denoted by ρ

,andthesetoffalseonesbyρ

We say that a function f (x

,...,x

)fromP

preserves ρ, if the truth of every element

222 V. B. Kudryavtsev

ρ(a

,...,a

),ρ(a

,...,a

),...,ρ(a

,...,

) implies the truth of ρ(f (a

,...,a

f(a

,...,a

),...,f(a

,...,

)).

AsetM of functions from P

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 P Let the truth region of a predicate ρ(y

) be the diagram of a permutation σ(x)

from P

, 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 E

= E

∪E

∪···∪E

,where1≤ t ≤ l, E

∩E

= ∅ for i = j.Weconsider

the predicate ρ(y

) that is true precisely on those collections for which a, b ∈ E

for some i. The family E consists exactly of all such predicates for the decompositions

indicated.

Family L Let l = p

,wherep is prime, and let G = E

, + be an Abelian group whose

every non-zero element has the order p, i.e., G is an elementary p-group.

For p = 2 we consider the predicate ρ

) which is true exactly on those

collections for which y

= y

.InthiscaseL consists exactly of those predicates

which correspond to all indicated elementary 2-groups G.

For p = 2 we consider the predicate ρ

) which is true exactly on those col-

lections for which y

−1

+ y

), where 2

−1

denotes the number from E

for which

2 · 2

−1

≡ 1(modp). In this case L consists exactly of those predicates ρ

which

correspond to all indicated elementary p-groups.

Family B Let h, m be natural numbers such that h ≥ 3, m ≥ 1, h

≤ l,andletϕ(x)bean

arbitrary mapping of E

into E

.Leta ∈ E

;denoteby[a]

the l-th coeﬃcient in

the decomposition

a =

m−1



l=0

[a]

, [a]

∈ E

We consider the predicate ρ(y

,...,y

) which is true exactly on those collections

for which the collection ([ϕ(a

)]

, [ϕ(a

)]

,...,[ϕ(a

)]

) is nondiﬀerent-valued for any l

from E

, 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 Apredicateρ(y

,...,y

), h ≥ 1, is reﬂexive if its truth follows from the

nondiﬀerent-valuedness of the collection of values of the variables, and it is symmetrical

if for any substitution t(u)ofthenumbers1, 2,...,h,

ρ(y

,...,y

)=ρ(y

t(1)

t(2)

,...,y

t(h)

The non-empty set of all elements c from E

such that for all values of the variables

ρ(y

,...,y

h−1

,c) = 1 is called the centre of the symmetrical predicate ρ.Apredicate

ρ is called central if it is symmetrical, reﬂexive and has a centre C such that C ⊂ E

The family Z consists exactly of all the central predicates ρ(y

,...,y

) such that

1 ≤ h ≤ l − 1.

On the automata functional systems 223

Family M A partial order on E

with one the greatest and one the smallest elements can

be assigned by a binary predicate ρ(y

). 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 .

3.7 Theorem The following relations are true:

(1) U(W )=Σ(P

);

(2) |U(W )|∼l · (l − 2 · [

]+1)· 2

(

l−1

[(l−1)/2]

)

Part (1) of this assertion was gradually established by the authors of the papers [10,11,21,

24, 26, 30, 32, 33], and the concluding study was carried out in [26]. Part (2) was established

in [7].

The sharp diﬀerence in the properties of P for l =2andl>2 led to the study of

diﬀerent variations of the main problems for P.f.s. such as testing 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 lattice of closed classes, etc.

Besides that, the objects of scientiﬁc investigation were generalizations of P

in the form of

P.f.s. of non-homogeneous functions, i.e., of functions depending on groups of variables whose

domains of deﬁnition are diﬀerent [18], and also functions whose variables, like the functions

themselves, take a countable number of values.

The study of the Cartesian products of such generalizations and of other cases has begun

(see [25]). We do not discuss these directions here. We consider only the generalizations of

functions from P

which appear if we take into account the time which is necessary for their

calculations.

4 Functions with delays

Let f(x

,...,x

) ∈ P

and t ∈ N

.Apair(f(x

,...,x

),t) is called a function f

with delay t and the set of all such pairs is denoted by

. We extend the operations η, τ,∆

and ' to

assuming that if µ is any of them, then µ((f,t)) = (µ(f),t). We introduce

one more operation ∗

that is called a synchronous substitution, assuming that for the pairs

(f,t), (f



), (f



),...,(f



) in which the sets of variables of the functions f

,...,f

are mutually disjoint the relation

(f,t) ∗

((f



), (f



),...,(f



)) = (f (f

,...,f

),t+ t



)

holds.

The set of operations η, τ,∆, ', ∗s is denoted by Ω

and is called the operations of

synchronous superposition.LetM ⊆

and J

Ω

(M)=M, then the f.s. M =(M, Ω

)is

called an iterative P.f.s. of functions with delays of kind l (P.f.s.f.d.).

Let us brieﬂy sum up the main results in the study of these f.s. [16, 18].

4.1 Theorem For a ﬁnitely-generated P.f.s.f.d. M of kind l the set Σ

(M) is ﬁnite and is

eﬀectively constructed for any l.

224 V. B. Kudryavtsev

4.2 Theorem For a ﬁnitely-generated P.f.s.f.d. of kind l the problems of completeness and

expressibility are algorithmically decidable for any l.

4.3 Theorem For every l from N

there exists a P.f.s.f.d. of kind l such that:

(1) there is a countable basis;

(2) there is a ﬁnite basis of an assigned power;

(3) there is no basis.

4.4 Corollary The lattice of closed classes in

has cardinality of continuum for any l.

An example of a ﬁnitely-generated P.f.s.f.d. is

, Ω

For

Theorem 4.1 can be reﬁned as follows. Denote by M

(1)

the set of all functions f

such that (f,t) ∈ M for some t.

4.5 Theorem AsetM ⊆

is complete in

,ifandonlyifJ

Ω

(1)

,andM ⊇

{(f,1)},wheref/∈ E

Let M =(M,Ω

)andM



⊂ M.WesaythatM



is weakly complete in M if for any

function f from M

(1)

there is t such that (f,t) ∈ J

Ω



). 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)istrue.

4.6 Theorem For a ﬁnitely-generated P.f.s.f.d. M =(M,Ω

) of kind l the following asser-

tions are true.

(1) The set Σ

W π

(M) is ﬁnite or countable.

(2) The set Σ

W π

(M) is weakly criterial.

(3) The set Σ

W π

(M) is constructed eﬀectively.

4.7 Theorem For a ﬁnitely-generated P.f.s.f.d. 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 [16, 25]. Let us

give here the description of the case l =2.

Let M ⊆ P

and M ∈{C

};wedenoteby

M the set of all pairs (f,t)such

that f ∈ M and t ∈ N

A function f (x

,...,x

)fromP

is called an α-, β-, γ-orδ-function if f (x,x,...,x)is

equal to x, 1, 0or¯x respectively. Let A, B, Γ,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,andt ∈ N

On the automata functional systems 225

Let i ∈{0, 1};wedenoteby

the set of all pairs of the form

(f,0), (¯ı, t +1), (i, t),

where f ∈ C

i+2

and t ∈ N

A function f is called even if f (x

,...,x

)=f(¯x

, ¯x

,..., ¯x

Let Y be the set of all even functions. Let

H be the set of all pairs of the form

(f,0), (ϕ, t +1),

where ϕ ∈ Y , f ∈ D

,andt ∈ N

For every r from N

we denote by

the set of pairs of the form

(f,(2t +1)2

), (ϕ, (2t +1)2

), (ψ, 0),

where f ∈ D, ϕ ∈ A, ψ ∈ A, t ∈ N

,ands ∈ N

\{0, 1, 2,...,r}.

For every r from N

we denote by

the set of all pairs of the form

(f,(2t +1)2

), (0,t), (1,t), (ϕ, (2t +1)2

), (ψ, 0),

where

f ∈ M, ϕ ∈ M, ψ ∈ M , t ∈ N

,ands ∈ N

\{0, 1, 2,...,r}.

Let

W = {

,...,

,...}.

4.8 Theorem [16] The equality Σ

Wπ

(

W holds.

We note that an explicit description of Σ

Wπ

(

W for any l exists only in the form of

separate families of weakly precomplete classes [2, 18].

From the point of view of content the modiﬁcations of the problem of completeness for

P.f.s.f.d. considered in [18] are of interest.

5 Automata functions

The extension of the functions of l-valued logic to functions with delays (considered in [24]) is

intermediate in the transition to the class of automaton functions, whose properties logically

look essentially more complex than those of functions with delays. In order to introduce the

notion of automaton function we shall need auxiliary notations and deﬁnitions.

Let C be a ﬁnite or countable set which is called an alphabet. A sequence of letters from

C is called a word if it is ﬁnite, and a superword if it is inﬁnite. The class of all such words

is denoted by C

∗

, and of all superwords, by C

.LetC = C

∗

∪ C

and ξ ∈ C.Theword

formed by the ﬁrst r letters from ξ is called a preﬁx for ξ and is labeled by ξ]

.LetA 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 (ξ(.LetA and B be alphabets and f : A

∗

→ B

∗

. The function

f is called determined (d. function) if for any ξ from A

∗

the equality (f(ξ)( = (ξ( is valid,

and for any ξ

and ξ

from A

∗

and any i such that 1 ≤ i ≤ min(|ξ

|, |ξ

|)ifξ

]

= ξ

]

,then

f(ξ

)]

= f(ξ

)]

. It is known that a d. function f can be recurrently represented by the

so-called canonical equations of the form

q(1) = q

q(t +1)=ϕ(q(t),a(t)),

b(t)=ψ(q(t),a(t)),t=1, 2,...,

(5.1)