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

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

Completeness of automaton mappings 83

or, equivalently, by taking the input as the ﬁrst variable and the state as the second variable,

δ(x

)=non(x

)andγ(x

)=et(x

, non(x

)).

This leads to the net given in Figure 1. The lower two basic elements realize the output

function γ whereas the upper element non realizes δ (where we have omitted the feedback

since δ does not depend on the second variable). Obviously, we can omit both non-elements

because the double negation does not change the value, but then we will not be following the

idea for the construction of a net from an automaton.

Figure 1: Logical net associated with the automaton A

of Example 2.4

Combining these constructions we get the following statement.

2.6 Theorem For a function F :({0, 1}

)

→{0, 1}

, the following statements are equiv-

alent:

(1) F is a sequential function;

(2) F is a induced by some automaton;

(3) F is associated with some logical net.

For a sequential function F :({0, 1}

)

∗

→{0, 1}

∗

,wecallm the arity of F and denote it

by arity(F ).

We designate the set of all sequential functions F :({0, 1}

)

∗

→{0, 1}

∗

(of arity m)by

and set

F =



m≥1

Let F be a function of F of arity m.Thenwehave

F (x

...x

)=y

...y

84 J. Dassow

where

∈{0, 1}

and y

∈{0, 1} for 1 ≤ i ≤ n.

Moreover,

=(x

,...,x

)for1≤ i ≤ n.

Then, for any i ≥ 1, there is a function ϕ

such that

= ϕ

,...,x

)=ϕ

,...,x

Further, for 1 ≤ j ≤ m,weset

= x

...x

and we call p

the input word of the j-th variable or the j-th input. Then we can also write

F (p)=F (p

,...p

For a Boolean function f : {0, 1}

→{0, 1},letF

(f)

be the sequential function with

(f)

,...,x

)=f(x

)f(x

) ...f(x

)

= f(x

,...,x

) ...f(x

,...,x

)

or, equivalently,

(f)

...,x

,...,x

)=f(x

,...,x

)

for i ≥ 1. Obviously, F

(f)

realizes f at any moment.

For a unary Boolean function f : {0, 1}→{0, 1} and a ∈{0, 1},wedenotebyF

(f;a)

the

sequential function with

(f;a)

...x

)=af(x

) f(x

) ...f(x

n−1

(f;a)

realizes f with delay 1 and has output a at the ﬁrst moment. Note that F

(id;1)

is the

sequential function associated with the logical net of type S.

We now introduce some operations on the set F, which are motivated by the deﬁnition

of logical nets.

For F ∈F

and G ∈F

,weset

(ζF)(p

,...,p

)=F (p

,...,p

(ηF)(p

,...,p

)=F (p

,...,p

(∆F )(p

,...,p

m−1

)=F (p

,...,p

m−1

(∇F )(p

,...,p

m+1

)=F (p

,...,p

(F ◦ G)(p

,...,p

m+k−1

)=F (G(p

,...p

),p

k+1

,...,p

k+m−1

)

By the operation ζ we produce a cyclic shift of the inputs, and η exchanges the ﬁrst two

inputs. It is well-known that by these two special permutations of the inputs we can generate

any permutation of the inputs. By ∆ we identify two inputs, i.e., their inputs coincide at any

moment. Combining ζ, η and ∆ we can identify an arbitrary set of inputs. Therefore ∆ can

be considered as the formal description of the ﬁrst operation for the construction of logical

Completeness of automaton mappings 85

nets. ∇ adds a variable, but the result does not depend on the input word of this variable.

◦ is the formal description of the substitution or superposition used as the second operation

for the construction of logical nets.

We now give a formal deﬁnition of the third operation for the construction of logical nets,

the feedback operation.

We say that F ∈F

depends on its ﬁrst variable in a delayed fashion if, for i ≥ 1, ϕ

does not depend on x

. (This reﬂects the requirement that any path from the ﬁrst input to

the output contains at least one element of type S.)

If F ∈F

depends on its ﬁrst variable delayed, we deﬁne ↑ F by

↑F

,...,x

)=ϕ

,...,x

↑F

,...,x

)=ϕ

(ϕ

↑F

),x

,...,x

↑F

),x

,...,x

,...,ϕ

t−1

↑F

t−1

),x

t−1,2

,...,x

t−1,m

,...,x

)

for t ≥ 2wherez

stands for the tuple (x

,...,x

Now we deﬁne the algebra

=(F, {ζ,η,∆, ∇, ◦, ↑}).

of sequential functions which will be studied in this paper. Since we do not expect misunder-

standings we shall use the notation F for the algebra, too, i.e., we shall not distinguish—in

the notation—between the algebra and its target set. The same will also be done for all other

algebras considered in this paper.

By [M ] we denote subalgebra generated by M ⊆Fin F

Sometimes we are also interested in the algebra without the feedback operation, i.e., we

consider the algebra



=(F, {ζ,η,∆, ∇, ◦}).

In this case, M denotes the subalgebra generated by M ⊆Fin F



Moreover, for k ≥ 2, we set

= {f | f : {0, 1,...,k− 1}

→{0, 1,...,k− 1},m≥ 1}.

is the set of all functions over a k-element set. P

is the set of Boolean functions. It is

easy to see that the operations ζ, η,∆,∇ and ◦ can be deﬁned in P

, k ≥ 2, too. Thus we

get the algebra

=(P

, {ζ,η,∆, ∇, ◦}).

2.2 Completeness in the algebra of sequential functions

In this subsection we recall the most important facts about classical completeness in F.We

start with a deﬁnition of the concept.

2.7 Deﬁnition A subset M of F is called complete (in F)iftheset[M ] generated by M is

86 J. Dassow

By the deﬁnition of logical nets, it is obvious that the set

M = {F

(non)

(et)

(vel)

(id;1)

}

is complete. If we delete F

(et)

, then the remaining set of sequential functions is complete,

too. The following theorem gives the numbers of elements which are possible for complete

sets which cannot be reduced.

2.8 Theorem For any n, there is a complete set M = {F

,...,F

} such that M \{F

}

is not complete.

For a proof of Theorem 2.8, we refer to [11]. Moreover, we mention that there is a

sequential function U ∈F

such that {U} is complete, as shown by Buevic [1].

2.9 Deﬁnition A subalgebra M is called maximal (in F), if there is no subalgebra N with

M ⊂ N ⊂F.

It is well-known from universal algebra that the subsets generating the whole set can

be characterized by the maximal subalgebras if the algebra is ﬁnitely generated. Thus we

immediately get the following theorem.

2.10 Theorem M is complete if and only if M is not contained in any maximal subalgebra.

The cardinality of maximal subalgebras of F has been determined by V. B. Kudrjavcev

[20].

2.11 Theorem The cardinality of the set of maximal subalgebras is the cardinality of the set

of real numbers.

Proof For a complete proof of the theorem, we refer to [20, 11]. Here we only mention

that maximal subalgebras are constructed which depend on a chosen subset of N.Sinceall

these maximal subalgebras are diﬀerent, one gets that there are at least as many maximal

subalgebras as subsets of N.

On the other hand, since the cardinality of F is countably inﬁnite, there are at most as

many subsets of F as subsets of N. Therefore we cannot have more maximal subalgebras as

subsets of N. 2

Obviously, by Theorem 2.11, the completeness criterion of Theorem 2.10 does not provide

an algorithm to decide the completeness of a ﬁnite set. Therefore we are interested in reducing

the number of maximal subalgebras which have to be taken into consideration. This is done

by the following theorem, but it also provides no algorithm.

2.12 Theorem There is a countable set N of maximal subalgebras such that M ⊂Fis

complete if and only if M is not contained in any algebra of N.

Proof Let M be a ﬁnite subset of F which is not complete. Then M ⊆ N(M )forsome

maximal subalgebra N(M ). We set

U = {N(M) | M is a ﬁnite incomplete subset of F}.

Since the number of ﬁnite subsets of F is countable, U is

countable.

Completeness of automaton mappings 87

Obviously, if M is complete, then M is not contained in any maximal subalgebra of F,

and thus M is not contained in any member of U.IfM is ﬁnite and incomplete, then M is

contained in an element of U. Therefore a ﬁnite subset M of F is complete if and only if it

is not contained in an element of the countable set U of maximal subalgebras. 2

The completeness criteria of Theorems 2.10 and 2.12, using maximal subalgebras, do not

give an algorithm to decide the completeness of a ﬁnite set. We shall now prove that there

is no such algorithm at all.

2.13 Theorem There is no algorithm to decide the completeness of a ﬁnite subset of F.

Proof The proof consists of a reduction to ﬁnite derivations of words in normal Post systems.

Thus we start with a deﬁnition of these systems.

A normal Post system is a triple

G =({x

,...,x

},µ,{w

,...,w

})

where

•{x

,...,x

} is a ﬁnite alphabet,

• µ is a positive integer,

• for 1 ≤ i ≤ n, w

is a word over {x

,...,x

} associated with the i-th letter x

We introduce a derivation relation with respect to G as follows. For two words u and v

over {x

,...,x

},wesaythatu =⇒ v if and only if

u = x

...x

,r≥ µ, v = x

µ+1

µ+2

...x

i.e., we cancel the ﬁrst µ letters of u and add at the end the word associated with the ﬁrst

letter of u. Thus any word w induces a derivation

w = w

=⇒ w

=⇒ ... =⇒ w

=⇒ ...

Such a derivation can be ﬁnite or inﬁnite. Finiteness occurs if |w

| <µfor some i (since we

can only perform a derivation step if the length of the word is at least µ). The following fact

is well-known [17].

Fact There is no algorithm which decides whether or not a given word w has a ﬁnite deriva-

tion with respect to a given normal Post system G.

We now consider the alphabet X = {0, 1, 2,x

,...,x

} of n + 3 letters. Further, let

be the set of all sequential functions mapping (X

)

into X

,andletS be the union

of all S

taken over m ∈ N. Obviously, we can form the algebra S with the same operations

as in F

. We note that there also is a function U ∈S

such that [{U}]=S (see the remark

after Theorem 2.8).

Let G be a normal Post system speciﬁed as above, and let w be an arbitrary word over

,...,x

88 J. Dassow

We now consider the functions F

∈S

, F

∈S

and F

∈S

with

...y

)=2w1

n−|w|−1

for n ≥|w| +1,

)=2

r+µ



where |u|≥µ, u =⇒ v, r + |u| + s = r + µ + |v| + s



)=2

r+|u|

where |u| <µ,

)=U(q

Note that the functions F

, F

and F

are not completely deﬁned. We complete their

deﬁnitions by the following two conditions:

• if p is a preﬁx of an input word mentioned in the conditions above, then the output is

the corresponding preﬁx of the output;

• if t is the ﬁrst moment where the input word is not a preﬁx of a word mentioned in the

conditions above, then the output is 0 at all moments j ≥ t.

Then F

is a constant function which essentially produces the word w, F

simulates a

derivation step according to G,andF

simulates the function U.

It is easy to construct automata which induce the functions F

, F

and F

(using an

automaton inducing U). Therefore F

, F

and F

are sequential functions.

We now prove that {F

} is complete in S if and only if w has a ﬁnite derivation.

Assume that w has a ﬁnite derivation, and let w

be the word of length smaller than µ.

Then the sequential function

H = F

◦ (F

◦(...(F

  

i+1 times

◦F

) ...))

produces as output a ﬁnite preﬁx of the inﬁnite word 2

1+iµ+|w

11 ... Thus ∆(F

◦H)coincides

with the function U which is complete for S.Thus{F



} is complete, too.

The idea of the converse statement is an analysis of the way to obtain U from the elements

of the complete set {F

}. The last element of the corresponding net cannot be F

or F

since they give the output 2 or 0 at the ﬁrst moment which does not hold for U.Thus

the last element is F

. Going backwards we analogously show that essentially the net has to

have the form given above for U.Thusw has to have a ﬁnite derivation for w. A detailed

proof of this fact is given in [11].

Thus the completeness of a ﬁnite subset of S cannot be decided. To transform this to F

we code the values of X by binary words and modify F

, F

and F

accordingly. 2

We also recall some facts on completeness in the algebra P

(for the proofs we refer to

[16]).

A function f ∈ P

is called linear if there are elements c

,...,c

of {0, 1} such that

f(x

,...,x

)=c

+ c

+ ···+ c

mod 2.

By Lin we denote the set of all linear functions of P

For i ∈{0, 1}, Q

is the set of all functions f such that

f(x

...,x

)=f(y

,...,y

)=i

Completeness of automaton mappings 89

implies the existence of j,1≤ j ≤ n,withx

= y

= i.

Further we set

= {f | f (0, 0,...,0) = 0},

= {f | f (1, 1,...,1) = 1},

Sd = {f | f(x

,...,x

) = non(f(non(x

), non(x

),...,non(x

)))},

Mon = {f | x

≤ y

for 1 ≤ i ≤ n implies f (x

,...x

) ≤ f(y

,...,y

)}.

We also say that the functions in T

, T

, Sd and Mon are 0-preserving, 1-preserving, self-dual

and monotone, respectively.

The following completeness criteria hold.

2.14 Theorem

(1) AsubsetM of P

is complete in P

if and only if it is not contained in T

, T

, Lin, Sd

and Mon.

(2) For i ∈{0, 1}, a subset M of T

satisﬁes M = T

if and only if M is not contained in

, Lin ∩ T

, Sd ∩ T

, Mon ∩ T

and T

∩ T

2.3 Completeness with respect to equivalence relations

In this subsection we deﬁne a modiﬁed concept of completeness which will be the subject

of this paper. Although this notion has not been discussed before, most modiﬁcations of

completeness which have been investigated in recent years (especially in the seventies) are

covered by our concept.

2.15 Deﬁnition Let  be an equivalence relation on F.

(1) A subalgebra M of F is called a -algebra if and only if M ∩ K = ∅ for all equivalence

classes K of .

(2) A subset M of F is called -complete if and only if [M]isa-algebra.

The requirement of -completeness does not require for the generation of any sequential

function; it is suﬃcient to generate a representive of any equivalence class.

Since we are interested in obtaining algebraic completeness criteria (as given in Theo-

rem 2.10) for -completeness too, we deﬁne a notion analogous to maximality.

2.16 Deﬁnition Let  be an equivalence relation on F. A subalgebra M of F is called

-maximal if and only if the following conditions are satisﬁed:

• M is not a -algebra;

• any subalgebra N with M ⊂ N is a -algebra.

We illustrate these concepts by an example.

90 J. Dassow

2.17 Example We consider the equivalence relation 

deﬁned by



= {(F, G) | arity(F )=arity(G),F((0, 0,...,0)) = G((0, 0,...,0))}.

It is easy to see that the equivalence classes of 

are given by

n,a

= {F | arity(F )=n and F ((0, 0,...,0)) = a},

where n ∈ N and a ∈{0, 1}.

Obviously, F is a 

-algebra (this statement holds for any equivalence relation). But there

are further 

-algebras. Here we only present the subalgebra with the target set

Q = {F | F

(q)=0

|q|

for |p|≥1},

which is the set of all sequential functions where, for t ≥ 2, ϕ

is the constant k

.Itiseasy

to see that these functions form a subalgebra. Moreover, it is a 

-subalgebra since, for any

Boolean function f, it contains a sequential function F with ϕ

= f.

Since by applications of ∇ and ∆, we can obtain functions of arbitrary arity, M is 

complete if and only if [M] contains at least one F with F((0, 0,...,0)) = 0 and at least one

G with G((0, 0,...,0)) = 1.

If M only contains functions F with F ((0, 0,...,0)) = 0, then this holds for [M]too.

Therefore M contains a function G with G((0, 0,...,0)) = 1. Let G



be the sequential

function obtained from G by identiﬁcation of all inputs.

First let us assume that G(1, 1,...,1) = 0. Then, ϕ



=non. Thusϕ



◦G



= id, i.e.,



◦G



)(0) = 0. Thus M is 

-complete.

We now assume that ϕ

(1, 1,...,1) = 1 and that the function ϕ

is not a constant.

Then there is a tuple (a

,...,a

)withϕ

,...,a

)=0. For1≤ i ≤ r, we deﬁne

the sequential functions H



(id)

if a



if a

Then the sequential function H ∈F

deﬁned by

H(p)=G(H

(p),H

(p),...,H

(p))

satisﬁes ϕ

(0) = 0. Thus M is also 

-complete in this case.

Finally, let us assume that ϕ

is the (r-ary) constant k

.ThenM has to contain a

function F with F ((0, 0,...,0)) = 0 in order to be 

-complete.

Thus we have the following decidable criterion for 

-completeness: M is 

-complete if

and only if M contains at least one function G where G((0, 0,...,0)) = 1 and ϕ

is not a

constant or M contains at least a function G where ϕ

is the constant k

and one F with

F ((0, 0,...,0)) = 0.

By this criterion (or already by the deﬁnition),

= {F | F ((0, 0,...,0)) = 0}

is an example for a 

-maximal subalgebra.

Completeness of automaton mappings 91

3 Completeness with respect to congruence relations

3.1 Congruence relations on F

From the algebraic point of view congruence relations are the most interesting equivalence

relations since they can be used for structural characterizations, to induce a quotient algebra

and appear at least implicitly in many other concepts.

Therefore it is of great interest to study completeness with respect to congruence relations.

As a ﬁrst step we have to know all congruence relations on F. In this subsection we prove

that there are only four types of congruence relations.

We deﬁne the following relations on F:

• the complete relation σ

= {(F, G) | F, G ∈F},

• the equality relation σ

= {(F, G) | F = G},

• the arity relation σ

= {(F, G) | arity(F )=arity(G)},

• for any t ∈ N,thet-bounded equality relation

= {(F, G) | arity(F )=arity(G)andF (p)=G(p) for all p with |p|≤t}.

The easy proof of the following statement is left to the reader.

3.1 Lemma σ

, σ

and σ

for t ≥ 1 are congruence relations on F



as well as on F.

We now prove that there are no other congruence relations on F

and F



3.2 Lemma Let σ be a congruence relation on F



such that (F, G) ∈ σ holds for two sequen-

tial functions F and G of diﬀerent arity. Then σ coincides with the complete relation.

Proof We omit the proof which can be given analogously to Lemma 1 in [13] and Lemma 1

in [22]. 2

3.3 Theorem

(1) σ

, σ

and σ

for t ≥ 1 are the only congruence relations on F



(2) σ

, σ

and σ

for t ≥ 1 are the only congruence relations on F.

Proof We only give the proof of the ﬁrst statement. The second statement follows from

Lemma 3.1 since additional operations can only delete some congruence relations.

Let σ be a congruence relation on F



such that σ is not the complete relation and not the

equality relation. We deﬁne t ∈ N

as the integer such that the following two conditions are

satisﬁed:

• (F



) ∈ σ implies F



(q)=G



(q) for all words q with |q|≤t;

• there are two sequential functions F and G and a word p of length t +1 such that

(F, G) ∈ σ and F(p) = G(p).

92 J. Dassow

By our assumptions on σ such a number exists. We assume that t ≥ 1. Then σ is a

reﬁnement of the t-bounded equality since the arities of functions in relation have to coincide

by Lemma 3.2. Let r =arity(F )=arity(G).

Let p =(p

,...,p

)andp

= x

...x

t+1,j

for 1 ≤ j ≤ r.For1≤ i ≤ r,letF

the sequential function of F

such that



if k ≤ t +1,

0ifk>t+1.

Then we consider the sequential functions F



and G



deﬁned by



(u)=F (F

(u),F

(u),...,F

(u)) and G



(u)=G(F

(u),F

(u),...,F

(u)).

Clearly, F



and G



are constant functions and



,...,x

)=ϕ



,...,x

)forl = t +1,

y = ϕ

t+1



,...,x

t+1

) = ϕ

t+1



,...,x

t+1

)=z.

Moreover, (F



) ∈ σ.

Let H be the binary sequential function such that

((v

), (v

),...,(v

)) =

⎧

⎪

⎨

⎪

⎩

if l ≤ t,

if l ≥ t +1,v

2,t+1

= y,

0ifl ≥ t +1,v

2,t+1

= z.

If the value of the second input at moment t +1 isy, then the output of H is the ﬁrst input

at every moment. Otherwise, the output is 0 at any moment j ≥ t +1.

For an arbitrary sequential function R ∈F

, we now deﬁne the sequential functions H

and H

,...,q

)=H(R(q

,...,q

),F



)),

,...,q

)=H(R(q

,...,q

),G



)).

Obviously, we have (H

) ∈ σ. By the deﬁnition of H and y = ϕ

t+1



,...,x

t+1

= R. H

coincides with R at the ﬁrst t moments and has the output 0 at the other

moments.

Now assume that (R, S) ∈ σ

for two functions of F

.ThenR and S coincide at the ﬁrst

t moments. Thus H

= H

. Therefore we have the relations

R = H

, (H

) ∈ σ, H

= H

, (H

) ∈ σ, H

= S

which implies that (R, S) ∈ σ. Hence σ

is a reﬁnement of σ too.

Thus σ = σ

If t = 0, then we conclude analogously that σ is the arity relation. 2

We note that the relations σ

for t ≥ 1 are not only of interest because they are congruence

relations. Practically we cannot observe an inﬁnite behaviour of an automaton, i.e., there is

a bound t and we can restrict our observations to the behaviour at the ﬁrst t moments. Thus

we are only interested in sequential function up to σ

-equivalence.