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

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

226 V. B. Kudryavtsev

where the parameter q is called a state of f and takes values in 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 α from the following way:

(1) b(1) = ψ(q(1),a(1)), where q(1) = q

;

(2) 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 E

, i.e., A =(E

)

and B =(E

)

,wheren, m, p ∈ N . In that case it is convenient to turn from a one-place

d. function f (x)oftheformf :((E

)

∗

→ ((E

)

∗

to an n-ary d. function f (x

,...,x

)

of the form f



:((E

)

∗

)

→ ((E

)

∗

)

in the following way. Let ζ

∈ (E

∗

)andf(ζ

)=ζ



where

= c

(1)c

(2) ...c

(r),ζ



= c



(1)c



(2) ...c



(r),

in addition,

(t)=(e

(t),e

(t),...,e

(t)),c



(t)=(e



(t),e



(t),...,e



(t)),

where 1 ≤ t ≤ r.Let

= e

(1)e

(2) ...e

(r)andζ



= e



(1)e



(2) ...e



(r),

where 1 ≤ i ≤ n and 1 ≤ j ≤ m.

Figure 2

Now we assume that



(ζ

,ζ

,...,ζ

)=(ζ



,ζ



,...,ζ



The function f



is actually obtained from f only at the cost of presenting the matrices formed

by vector-letters (rows) of words ζ

and, respectively, ζ



as matrices formed by the columns.

On the automata functional systems 227

Canonical equations (5.2) for f



are obtained from (5.1) by replacing all the parameters there

with the corresponding vector values, i.e.,

q(1) = q

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

(t),...,e

(t)),

(t)=ψ

(q(t),e

(t),...,e

(t)),t=1, 2,..., j =1, 2,...,m.

(5.2)

The function f



is considered to be an interpretation of f and is called an automaton func-

tion (a. function). The parameters n and m are called, respectively, the locality and the

dimensionality of the a. function, and the cardinality of the set of values of the parameter q

is called the number of states. The signiﬁcant interpretation of the a. function



,...,x

)=(y

,...,y

)

is the functioning of the technical device F shown in Fig. 2. Here the input arrows are labelled

by the letters x

,i =1,...,n, and the output ones, by the letters y

, j =1, 2,...,m.Itis

assumed that F functions at the discrete moments of time t =1, 2,.... At these moments

every input x

and output y

can take values in E

; the device itself may be in states that are

coded by values from Q, these states are also called 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 (5.2).

Denote by P

n,m

a,l

the class of all a. functions with the given parameters n and m from N.

Let

a,l



n,m≥1

n,m

a,l

We extend the operations η, τ,∆, ∇ to P

a,l

, and also introduce some other operations.

Let f



,...,x

)=(y

,...,y

), then

(π



)(x

,...,x

)=f



,...,x

where f



,...,x

) coincides with the value y

in f



,...,x

Let f



n+1

n+2

,...,x

n+v

)=(y

m+1

,...,y

m+w

), then



σf



)(x

,...,x

n+1

n+2

,...,x

n+v

)=(f



,...,x



n+1

n+2

,...,x

n+v

)) = (y

,...,y

m+1

m+2

,...,y

m+w

Let u be such that m +1≤ u ≤ m + u,then



∗



)(x

,...,x

n+1

n+2

,...,x

n+v

)=(z

,...,z

m+w−1

where z

= f



∗f



for j =1, 2,...,m and z



= f





n+1

n+2

,...,x

n+v

)forj



= m +2,m+

3,...,m+ t.

The operations π and σ are called, respectively, projection and union, and the operation

of the form ∗

is the extension of the operation ∗

from one-dimensional functions to vector

functions and, as before, is called substitution.

In total the operations η,τ,∆, ∇,π,σ and ∗

are called operations of extended superposi-

tion and is denoted by Σ

228 V. B. Kudryavtsev

Let us introduce one more operation on a. functions, which is called feedback and is

denoted by F.

It is said that an a. function f



is of type i −j if for f



there is a system of kind (5.2) such

that the function ψ

(q,e

,...,e

) ﬁctitiously depends on e

.Letf



be such an a. function;

we consider a function of the form



)(x

,...,x

i−1

i+1

,...,x

)=(y

,...,y

j−1

j+1

,...,y

which is determined in the following way. Let words of the form

= e

(1)e

(2) ...e

(r),

where l =1, 2,...,i−1,i+1,...,nbe given. Then with the help of (5.2), using the collection

(1),e

(1),...,e

i−1

(1),e

i+1

(1),...,e

(1)), it is possible to calculate the value b

(1). Now

in (5.2) we substitute b

(1) for e

(1); after that it is possible to calculate the collections (q(2))

and (b

(1),b

(1),...,b

(1)). Then it is also possible to calculate the value b

(2), using the

collection

(2),e

(2),...,e

i−1

(2),e

i+1

(2),...,e

(2)).

Again, the substitution of e

(2) for b

(2) in (5.2) makes it possible to calculate the collections

(q(3)) and (b

(2),b

(2),...,b

(2)) and so on.

Now we assume that



)(ζ

,ζ

,...,ζ

i−1

,ζ

i+1

,...,ζ

)=(ζ



,ζ



,...,ζ



i−1

,ζ



i+2

,...,ζ



where ζ



= b



(1)b



(2) ...b



(r)andl



=1, 2,...,j−1,j+1,...,m. Suppose that Ω

es,F

=Ω

∪

{F }. The class of operations Ω

es,F

is called composition. It is said that an a. function f



from

a,l

is a ﬁnite automata function (f.a. function) if the alphabet Q in system (5.2) determining

this function is ﬁnite. Denote by P

n,m

a,l,k

the class of all f.a. functions with parameters n and

m. Suppose that

a,l,k



n,m≥1

n,m

a,l,k

It is said that an a. function is true (t.a. function) if the alphabet Q in system (5.2)

determining this function is a one-element set. We denote by P

n,m

a,l,t

and P

n,m

a,l,k,t

the classes of

all true a. functions and of true f.a. functions (t.f.a. functions), respectively, with parameters

n and m. Suppose that

a,l,t



n,m≥1

n,m

a,l,t

a,l,k,t



n,m≥1

n,m

a,l,k,t

From the content point of view, true a. 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 P

with regard to time t that runs over the values

1, 2,.... At each moment of time the dependence of the value of the function on the values

of the variables is the same.

Thus, a P.f.s. (P

, Ω

) actually leads to P

a,l,t

=(P

a,l,t

, Ω

), if we extend the object P

the set of vector functions of l-valued logic and, respectively, extend the operations to Ω

On the automata functional systems 229

We also note that a function with delay is interpreted as the functioning of such device

F with n inputs and one output whose value b(t)forsomeτ from N

and f (x

,...,x

)

from P

is determined at any moment t ≥ τ +1 bytherelation

b(t)=f(a

(t − τ),a

(t − τ ),...,a

(t − τ ))

that, evidently, can be described by a system of form (5.2).

Let M ⊆ P

a,l

;thenforJ

Ω

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

), and for J

Ω

es,F

(M)=M the

f.s. M =(M, Ω

es,F

) are called iterative P.f.s. of automaton functions (P.f.s.a.f.). Examples

of such f.s. are f.s. of the form P

a,l,t

.Foragivenl ∈ N

, the main P.f.s.a.f. are

a,l,k

=(P

a,l,k

, Ω

), P

∗

a,l,k

=(P

a,l,k

, Ω

es,F

a,l

=(P

a,l

, Ω

), P

∗

a,l

=(P

a,l

, Ω

es,F

(5.3)

Let us give the main results concerning our problems for P.f.s.a.f.

5.1 Theorem [19] For any l from N

among the main P.f.s.a.f. only f.s. P

∗

a,l,k

is ﬁnitely

generated.

5.2 Theorem [17] For any l from N and m from N

in P

∗

a,l,k

there exists a countable set

of bases of power m.

An a. function forming a complete system in M is called a Sheﬀer function.Furthersim-

pliﬁcation of the basis is achieved by minimization of the number of variables, dimensionality

and the number of states of a Sheﬀer a. function. The next assertion gives the ﬁnal answer

concerning the form of the simplest, in this sense, Sheﬀer a. functions.

5.3 Theorem [28] For every l from N

in P

∗

a,l,k

there exist Sheﬀer one-dimensional a. func-

tions of two variables and with two states.

For the other two main P.f.s.a.f. the following assertion gives the answer to the basis

problem.

5.4 Theorem [19] For any l from N

in P

a,l

and P

∗

a,l

, there are no bases, in P

a,l,k

there

is a countable basis as well as a complete system containing no basis.

As for the completeness problem, the situation is described by the following assertions.

5.5 Theorem [3, 19] For the main P.f.s.a.f. the set Σ

(M) forms a c-system only for

M = P

∗

a,l,k

for any l from N

5.6 Theorem [17] For any l from N

the set Σ

(M) has cardinality of continuum for

M∈{P

a,l,k

, P

∗

a,l,k

} and hypercontinuum for M∈{P

a,l

, P

∗

a,l

As a corollary we obtain that the corresponding lattices of closed classes in the main

P.f.s.a.f. have the cardinalities mentioned in Theorem 5.6.

AsystemΣ



⊆ Σ(P

∗

a,l,k

) is called c-criterial if any ﬁnite set M ⊆P

a,l,k

is complete if and

only if for any set K ∈ Σ



the condition M ⊆ K is valid.

230 V. B. Kudryavtsev

5.7 Theorem [17] In P

∗

a,l,k

there exist countable c-criterial systems of the form Σ



⊆

∗

a,l,k

) for any l from N

It should be pointed out that in the general case assigning a. functions from P

a,l

is not

eﬃcient; therefore the problem of expressibility and completeness can be posed only for

eﬀectively assigned systems.

5.8 Theorem [15] The problem of expressibility for eﬀectively assigned ﬁnite systems of

a. functions in the main P.f.s.a.f. and the problem of completeness in P

a,l

are not algorith-

mically decidable for any l from N

Thus the extension of the functional possibilities of a. 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 a. functions. The study of the nature of this

complexity was carried out in diﬀerent directions.

Here we dwell on the problem of approximate completeness and on the problem of com-

pleteness of specially enriched systems of a. functions.

The ﬁrst of these problems has two modiﬁcations: the problem of r-completeness, r ∈ N,

and the problem of approximate completeness (A-completeness), to which the next section

is devoted. We call attention to special f.s.’s P

, P

and P

that are subalgebras of

the corresponding main P.f.s.a.f. from (5.3). Each of them consists of all one-place and one-

dimensional a. functions from the main P.f.s., and operations employed in them are the same

as in the corresponding P.f.s.a.f., except the operations σ and π. As has been established

in [1, 19], they have no bases. Besides that P

contains a subalgebra P



,ofallone-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 [2], i.e., a ﬁnitely-generated group in which the orders

of the elements are ﬁnite, but are not bounded in totality. Still open are questions of the

existence of bases in P



, as well as the problem of algorithmic decidability of the property of

ﬁniteness 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 also remain valid for the case where the value l is extended to

countable in the f.s. of functions; in this way we generalize a. functions.

6 Conditions of r-andA-completeness for a. functions

A. functions f and g are r-equivalent if they coincide on all input words of length r (in this

case we write frg)andA-equivalent if frgfor any r in N.

On the set B(P

a,l

) we introduce a relation ∆

such that M ∆



for M,M



⊆ P

a,l

,iffor

every function f from M there is g from M



such that frg. It is clear that this relation forms

a preorder and, consequently, can be represented as a relation of partial order on equivalence

classes including all elements M and M



for which the relations M ∆



and M



∆

M are

valid;inthiscasewewriteMrM



and the elements themselves are called r-equivalent.

On B(P

a,l

) we introduce one more relation, assuming that for M,M



⊆ P

a,l

the relation

M ∆



is fulﬁlled if MrM



for any r from N . This relation is also a preorder for

representatives M and M



of its equivalence class, and when M ∆



and M



∆

M we

write MAM



and the representatives themselves are called A-equivalent.

On the automata functional systems 231

6.1 Theorem [8] For any M ⊆ P

a,l

and r ∈ N

Ω

(M) rJ

Ω

es,F

(M),J

Ω

(M) AJ

Ω

es,F

(M).

Thus the actions of the operators J

Ω

(M)andJ

Ω

es,F

(M)coincideuptor-andA-

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

Let M,M



⊆ P

a,l

.ItissaidthatM is r-expressible by M



if M ∆

Ω



), and

A-expressible by M



if M ∆

Ω



6.2 Theorem For eﬀectively assigned ﬁnite sets M,M



⊆ P

a,l

, the relation

M ∆

Ω



)

is algorithmically decidable for any r in N.

6.3 Theorem [7] For ﬁnite sets M, M



⊆ P

a,l,k

, the relation M ∆

Ω



) is algorith-

mically undecidable.

Let M ⊆ P

A,l

and MAJ

Ω



). The set M



⊆ M is called r-complete in M if

Ω



) rM and A-complete if J

Ω



) AM.

6.4 Theorem If M ⊆ P

a,l

, MAJ

Ω

(M), M is decidable, there is a ﬁnite A-complete subset

of M and r ∈ N, then there exists an algorithm determining whether any ﬁnite decidable

subset M



⊆ M is r-complete in M.

In fact this theorem follows from Theorem 3.2; we verify this fact in the following way.

Let f ∈ P

a,l

and r ∈ N. Consider the set E

assuming that its elements are coded by the

words of length r in the alphabet E

. Then, examining the function f from P

a,l

only on

words of length r, we can consider it to belong to P

. Thus, from examining a. 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 P

a,l,k

a,l

6.5 Theorem The conditions of r-completeness and of A-completeness, respectively, coin-

cide for all main P.f.s.a.f.’s.

We point out an essential diﬀerence between the notions of r-completeness and A-com-

pleteness which is given in the following assertion.

6.6 Theorem In each of the main P.f.s.a.f. there exists ﬁnite A-complete systems and count-

able A-complete systems containing no ﬁnite A-complete subsystems.

The diﬀerence in the notions of r-completeness and A-completeness appears in the fol-

lowing assertion.

6.7 Theorem [7] If M ⊆ P

a,l,k

and M is ﬁnite, then there is no algorithm establishing

whether M is A-complete in P

a,l,k

232 V. B. Kudryavtsev

At the same time there is some similarity of the notions of r-andA-completeness and

it reveals itself in the approach to solving problems of r-andA-completeness in terms of

precomplete classes.

If M ⊆ P

a,l

, MAJ

Ω

(M)andM



⊆ M,thenM



is called r-precomplete in M if it is

not r-complete in M , but for any function f from M \M



the set M



∪{f} is r-complete in

M. The notion of an A-precomplete is introduced analogously. Let



π,r

(M)and



π,A

(M)

be the sets of all r-precomplete and A-precomplete sets in M respectively.

6.8 Theorem If M ⊆ P

a,l

and MAJ

Ω

(M),then



π,A

(M)=



r≥1



π,r

(M).

6.9 Theorem If λ ∈{r, A}, r ∈ N, M ⊆ P

a,l

, MAJ

Ω

(M) in M where it is a ﬁnite

λ-complete subset, and M



⊆ M,thenM



is λ-complete in M if and only if M



⊂ K for any

K ∈



π,λ

This assertion with regard to Theorems 6.6 and 6.8 reduces the solution of r-andA-

completeness problems in the main P.f.s.a.f. to the description of the set



π,r

a,l

(this fact

was obtained in [8]). Let us give this description.

Let t ∈ N ;denotebyE

the set of all words  = e(1)e(2) ...e(t)oflengtht in the

alphabet E

.Forh ∈ N and T =(t

,...t

), where t

∈ N , i =1,...h, we put E

×E

×···×E

, T ∈ N

.Letρ(y

,...y

)beanh-ary predicate whose arguments y

take values in E

, i =1,...h. As previously, let ρ

and ρ

be, respectively, the sets of true

and false collections of values of the variables for ρ. We say that a function f (x

,...x

)

from P

a,l

preserves ρ if the truth of the expression

ρ(f(α

,α

,...,α

),f(α

,α

,...,α

),...,f(α

,α

,...,α

))

follows from the truth of each element of the row

ρ(α

,α

,...,α

),ρ(α

,α

,...,α

),...,ρ(α

,α

,...,α

We denote the class of all such functions by U

(ρ).

We introduce the function ν : E

∗

× E

∗

→ N

, putting for 

= E

, 

= E

,and

t =min(t

ν(

,

⎧

⎪

⎨

⎪

⎩

0, if e

(1) = e

(1),...,e

(t)=e

(t),

i, if 1 ≤ i ≤ t −1ande

(1) = e

(1),...,e

(t − i)=e

(t − i),

but e

(t − i +1)= e

(t − i +1),

t, if e

(1) = e

(1).

We deﬁne the relation of preorder ≤ on the set E

Let A =(α

,α

,...,α

)andA



=(α



,α



,...,α



)beelementsfromE

.Wewrite



≤ A,ifν(α



,α



) ≤ ν(α

,α

) for any i, j ∈ N

Let t



=max{t

,...,t

}, h ≤ l

,andt



≥ 2; if l = 2, then we put h =2. Forh ≥ 2, let

ν(α

,α

) =0,i= j, in A.

On the automata functional systems 233

The set of all A



such that A



≤ A is called the ν-set determined by the element A.We

denote this set by ξ. ξ is divided into two subsets: ξ

(m)

consisting of all maximal elements

with respect to the relation ≤ and ξ

(m)

containing the rest of the elements in ξ. Thus, for

h =1wehaveξ

(m)

= ∅. It is clear that the value ν =(α

,α

) does not depend on the choice

of A from ξ

(m)

; therefore instead of ν =(α

,α

)wewriteν =(i, j).

For l ≥ 2andt ≥ 1 we indicate seven families of predicates.

Let h ≥ 1, T =(t

,...,t

)andξ ⊆ E

. A substitution γ of the numbers 1, 2,...,h is

called a ξ-substitution if (α

γ(1)

,α

γ(2)

,...,α

γ(h)

) ∈ ξ for any (α

,α

,...,α

)inξ.

Let s ≥ 1; we say that the set

{(α

,α

,...,α

), (α

,α

,...,α

),...,(α

,α

,...,α

)}

of elements from E

is ξ-consistent if there exists a collection of ξ-substitutions γ

,γ

,...,γ

such that ν(i, j) ≤ ν(α

(i),α

(j)) for any q and p in N

,andanyi and j in N

Let ρ(y

,...,y

) be a predicate for which ρ

⊆ ξ.Wesaythatρ is ξ-reﬂexive if

(m)

∈ ρ

,andξ-symmetrical if (α

γ(1)

,α

γ(2)

,...,α

γ(h)

) ∈ ρ

for any (α

,α

,...,α

)inρ

and any ξ-substitution γ.

A ξ-reﬂexive and ξ-symmetrical predicate ρ is called ξ-elementary if the set ξ \ ρ

is ξ-

consistent. For such ρ, A ∈ ξ \ρ

and i ∈ N

we determine subsets C

(A),Q

(A)and

(A)

of the set E

in the following way:

(1) a ∈ C

(A) if and only if there exists α



∈ E

such that ν(α

,α



) ≤ 1, α



)=a,and

any element (α



,α



,...,α



)fromξ is contained in ρ

;

(2) b ∈ Q

(A) if and only if there exists an element

(α

,α

,...,α

i−1

,α



,...,α

)inξ \ρ

such that ν(α

,α



) ≤ 1, α



)=b;

(3) The set 

(A)coincideswithC

(A)ifC

(A) = ∅ and with Q

(A)otherwise.

Let n ≥ 1andletR = {ρ

,ρ

,...,ρ

} be an arbitrary system of ξ-elementary predicates.

We say that R is T -consistent if Q

(A) = E

for any σ ∈ N

, i ∈ N

,andA ∈ ξ \ ρ

.We

say that R is W -consistent if for all σ, σ ∈ N

, i ∈ N

, A ∈ ξ \ ρ

, A



∈ ξ \ ρ

the sets

(A)andC



) are simultaneously either empty or not empty, and also if C

(A)=∅,

then for any b ∈ E

there exists j ∈ N

such that t

= t

, ν(i, j) ≤ 1, b ∈ Q

(A).

Let n ≥ 1, σ

∈ N

, A

=(α

,α

,...,α

), A

∈ ξ \ ρ

and j

∈ N

for i ∈ N

.Thenif

= σ



for i = i



and t

= t



, ν(α

,α



) ≤ 1, for all i, i



∈ N

and i



∈ N

\{1},and



i=1



)=∅,

then the system R is called Q-consistent.

Let n ≥ 2, i ∈ N

, σ

∈ N

and A

∈ ξ \ ρ

. We assume that ν(α

,α



) =1forall

j, j



∈ N

, j = j



.Lett

= t



and for all i



∈ N

, ν(α

,α

) ≤ 1forj>1, and



j=1



)=∅.

234 V. B. Kudryavtsev

We suppose that under these conditions there exists l

∈ N

, ν ∈ N

such that i

∈ N

the sets A

are ξ-consistent and



ν=1



)=∅.

Then we say that the system R is D-consistent.

The family of predicates Z

(r) This family is not empty for l ≥ 2andr ≥ 1. A

predicate ρ belongs to Z

(r) if and only if ρ

⊂ ξ, ξ ⊆ E

, T =(t

,...,t

), h ≥ 1,

max{t

,...,t

}≤r and for some m ≥ 1



i=1

where ρ

is ξ-elementary predicate, and the ρ

themselves form a T -, W -andQ-consistent

system, and for any j ∈ N

and A ∈ ξ \ρ

the set C

(A)isnon-empty.

The family of predicates J

(r) This family is not empty for r ≥ 1andl>2, and also for

r ≥ 2andl =2. Apredicateρ belongs to J

(r) if and only if ρ

⊆ ξ ⊆ E

, T =(t

,...,t

h ≥ 3, max{t

,...,t

}≤r,forsomem ≥ 1



i=1

where ρ

is ξ-elementary, and the ρ

themselves form a T -, W -andQ-consistent system; there

are numbers i, j, l ∈ N

, i = j, i = l, j = l, such that for A in ξ \ ρ

the set C

(A)isempty

for u ∈{i, j, l}.

The family of predicates D

(r) This family is not empty for r ≥ 1ifl>2andforr ≥ 2

and l =2. Apredicateρ belongs to J

(r) if and only if ρ

⊂ ξ ⊆ E

, T =(t

,...,t

h ≥ 2, max{t

,...,t

}≤r,forsomem ≥ 1



i=1

where ρ

is ξ-elementary, and the ρ

themselves form a T -, W -andQ-consistent system. For

any A ∈ ξ \ρ,thesetsC

(A)andC

(A)areempty.Ifh ≥ 3, then C

(A) = ∅ for any i from

;ifh =2,thenρ

∩ ξ

(m)

= ∅.

Further l ≥ 2, t ≥ 1, T =(t, t), ξ

⊆ E

, ξ

be a ν-subset and let ν

(1, 2) = 1.

The family of predicates M

(r) This family is not empty for l ≥ 2andr ≥ 1. A predicate

ρ belongs to M

(r) if and only if ρ

⊂ ξ

, t ≤ r,andρ

coincides with the relation of partial

order determined on E

and having exactly l

t−1

minimal and l

t−1

maximal elements.

On the automata functional systems 235

The family of predicates S

(r) This family is not empty for l ≥ 2andr ≥ 1. A

predicate ρ belongs to S

(r) if and only if ρ

⊂ ξ

, t ≤ r, and there is a substitution σ

decomposing into a product of cycles of equal prime length p ≥ 2 whose graph coincides

with ρ

, i.e., if a ∈ E

,then(a, σ

(a)) ∈ ρ

,andif(a

) ∈ ρ

,thena

= σ

Let

, t ≥ 1, be the class of all mappings φ of the set E

into the set of substitutions

on E

.Thevalueφ at a is denoted by φ

.LetΦ

⊆

,andletΦ

, consist of all φ such that

= φ



for v(a, a



) ≤ 1. Let h ∈{3, 4}, T

= {t,t,...,t}, K

⊆ E

and let K

consist

of all elements (a

,...,a

) such that v(a

) ≤ 1fori, j ∈ N

.Letl = p

,wherep is

prime, m ≥ 1, and let G = E

, + be an Abelian group whose every non-zero element has a

prime order p.Forp =2letl

∈ N

p−1

and 2l

=1 (modp).

The family of predicates L

(r) This family is not empty only for l = p

,wherep is

prime, m ≥ 1, t ≤ r.Apredicateρ belongs to L

(r) if and only if for some φ from Φ

, t ≤ r,

the following assertions are true:

(1) Let k = p

and p>2, then ρ

⊂ K

and (a

)fromK

belongs to ρ

if and only

if φ

(t)) = l

(φ

(t)) + φ

(t))).

(2) Let k = p

,thenρ

⊂ K

and (a

)fromK

belongs to ρ

if and only if

(t)) + φ

(t)) = φ

(t)) + φ

(t)).

We note that the families indicated for r = 1 coincide, respectively, with the known

families for P

, from Section 3. Let t>2, T =(t, t), and let

,beaµ-subset E

such that

(1, 1) = 2.

The family of predicates V

(r) This family is not empty for l ≥ 2andr ≥ 2. A predicate

ρ belongs to V

(r) if and only if ρ

⊂

, t ≤ r and (a

) ∈

(m)

∩ ρ

, if and only if

(t)=a

(t); there is φ from Φ

, such that the inclusion (a

) ∈

(m)

∩ ρ

is equivalent to

the existence of α in E

such that a

(t)=φ

(α)anda

(t)=φ

(t).

Let W

(r)=Z

(r) ∪J

(r) ∪D

(r) ∪M

(r) ∪S

(r) ∪L

(r) ∪V

(r), and let U(W

(r)) be the

set of classes of a. functions preserving predicates from W

(r).

6.10 Theorem [8] The equality Σ

π,r

a,l

)=U(W

(r)) is true.

7 Conditions of completeness for special systems of automa-

ton functions

Another way of studying the completeness properties of a. functions systems consists in

enriching the operations performed both on a. functions and on a. function systems which

are tested for completeness. We consider the second situation. Here two approaches are

of interest. The ﬁrst approach consists in considering Slupecki’s problem for f.s. P

a,l,k

and

the second one concerns such systems of a. functions in P

∗

a,l,k

that contain some closed class

of truth a. functions. Following [27], a ﬁnite system T of f.a. functions in P

a,l,k

is called a

Slupecki system if J

Ω

1,1

a,l,k

∪ T )=P

a,l,k

7.1 Theorem [25] For any l from N

there exist Slupecki systems of f.a. functions from

a,l,k