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

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

The structure of free algebras 73

elements of F

(n). So r =2

and Con(F

(n)) is a Boolean algebra with r coatoms. In the

decomposition of F

(n) into directly indecomposables,



j=1

, the unique coatom of the

congruence lattice of D

is the kernel of the homomorphism h

onto B in which h

−1

(0) = {0}

and h

−1

(1) = D

−{0}.ThevarietyS is congruence distributive, so it follows from known

results that for every A ∈S,ifA = A

× A

,thenCon A

∼

Con A

× Con A

.The

similarity types of τ

and τ

both include ∧, ∨,

∗∗

; while τ

includes the constant symbol 0

and τ

contains the constant symbol 1. The algebras A

for 1 ≤ j ≤ r are all 1-element

algebras and so the variety S

for q = 0 is the trivial variety T .Forq =1thealgebrasA

are term equivalent to distributive lattices with a top element 1 and the variety S

for q =1

is D

. For every j,wehaveX

= {x

: h

(pr

)) = k} for k =0, 1. Then D

hasasits

universe F

) ∪ F

In [2] general conditions on a variety V are presented and are proved to be suﬃcient to

force the well-behaved direct product decomposition of F

(n) into indecomposables described

in the previous paragraphs. We now sketch these results.

AvarietyV is said to have the Fraser-Horn Property (FHP) if there are no skew con-

gruences on ﬁnite products, i.e., for all A

, A

∈V,everyθ ∈ Con(A

× A

) is a product

congruence θ

× θ

with θ

∈ Con(A

)fork =1, 2. If V has FHP, then Con(A

× A

)

∼

Con A

×Con A

for all A

and A

in V. Various conditions that imply FHP are known. If

V is congruence distributive, then V has FHP. Fraser and Horn [10] give a Mal’cev condition

equivalent to FHP and they derive as a special case the following:

AvarietyV has FHP if there are binary terms + and · and elements 0 and 1 in

(3) such that for all z ∈ F

(3), we have z ·1=z +0=0+z = z and z ·0=0.

So, for example every variety of rings with unit has FHP.

A ﬁnite algebra A has the Apple Property (AP) if for all β ∈ Con A,ifβ<1

is a factor

congruence with A/β directly indecomposable, then the interval lattice [β,1

]inCon A has

exactly one coatom. A variety V has AP if every ﬁnite algebra in A has AP. Equivalently,

V has AP if every directly indecomposable ﬁnite algebra in V has a congruence lattice with

exactly one coatom. For example, a local ring has AP.

If an algebra or a variety has both FHP and AP, then we say it has FHAP. In [6] locally

ﬁnite varieties with FHAP are shown to have ﬁnitely generated free algebras with the rich

direct product structure described earlier in this section.

For any locally ﬁnite variety V let V

be the subvariety generated by all ﬁnite simple

algebras in V.WecallV

the prime variety of V. For arbitrary V little can be said about

. However, in the event that a locally ﬁnite variety has FHAP and satisﬁes one additional

condition, then the prime variety is especially well-behaved.

4.3 Theorem Let V be a locally ﬁnite variety with FHAP. Suppose every subalgebra of a

ﬁnite simple algebra in V is a product of simple algebras. Then all of the following hold:

(1) V

is congruence distributive.

(2) V

is congruence permutable.

(3) Every ﬁnite member of V

is a product of simple algebras.

74 J. Berman

(4) For every n the free algebras F

(n) and F

(n) have the same number of directly inde-

composable factors, and if r denotes this number, then it is possible to write

(n)=



j=1

and F

(n)=



j=1

with the D

and Q

directly indecomposable, so that if α

istheuniquecoatomof

Con(D

),thenD

/α

and Q

are isomorphic.

In the examples described in the earlier part of this section, the varieties satisfy the hypotheses

of this theorem and the prime variety in each case is, in fact, a variety generated by a

quasiprimal algebra.

4.4 Theorem Let V be a locally ﬁnite variety with FHAP. Suppose every subalgebra of a

ﬁnite simple algebra in V is a product of simple algebras. Let r, D

, Q

be as in Theorem 4.3

with h

: D

→ Q

a homomorphism with kernel α

.ForQ a ﬁnite simple algebra in V and

q ∈ Q,letτ

be the similarity type of all terms t for which t

(q,...,q)=q.Foreachj with

∼

Q,letA

be the algebra with universe h

−1

(q) ⊆ D

and operations those t in τ

,and

let V

be the variety generated by all A

.IfX

= {x

∈ X : h

(pr

)) = q}, then the algebra

contains a set that is the universe of an algebra isomorphic to F

The hypotheses of Theorems 4.3 and 4.4 are robust with many diﬀerent varieties satisfying

them. The examples alluded to earlier all satisfy them and thus Theorem 4.4 provides a

uniform explanation of the description of the directly indecomposable direct factors of the

ﬁnitely generated free algebras in those varieties.

In Theorem 4.4 we have that the universe of D

is the disjoint union of the universes of

the A

as q ranges over the elements of Q

and that A

contains a subalgebra isomorphic to

). For varieties such as Stone algebras, A

= F

)andsoD



q∈Q

This situation represents a lower bound for the size of the D

. Moreover, it is possible to

provide suﬃcient conditions on the behavior of the fundamental operations of V and V

that

guarantee that all the directly indecomposable D

have this minimal structure.

On the other hand, it is possible for the size of D

to exceed this lower bound. In [2] a

condition is given that if added to the hypotheses of Theorem 4.4 forces A

∼

(X)for

every q ∈ Q

. Thus, in this case D

is the disjoint union of |Q

| sets, each corresponding

to the universe of F

(X). Roughly speaking, this condition given in [2] is that for every

q, q



∈ Q

there is a unary term u



that maps A

onto A



. Note that if this condition holds,

then |D

| = |Q

|·|F

(n)|. An example of a variety in which this occurs is the variety V of

rings generated by Z

,forp any prime. As observed earlier, a variety of rings with unit

has FHP. The variety V is known to have AP and thus V has FHAP. The only simple ring

in V is Z

and so the prime variety V

is the variety generated by Z

.SoF

(n)

∼

)

Theorem 4.4 applies. The number of factors in the decomposition of F

(n) into directly

indecomposables is the same as that for F

(n), which is p

.Foreachq ∈ Z

it can be shown

that the variety V

is the variety generated by the p-element group in which all p elements are

constants. Thefreealgebraonn free generators for this variety is easily seen to have p

n+1

elements. For each q, q



∈ Z

the unary term u(x)=(x + q



− q)mod(p) can serve as u



So for each directly indecomposable factor D

of F

(n)wehave|D

| = p|F

(n)| = p

n+2

All the D

are isomorphic and thus |F

(n)| =(p

n+2

)

The structure of free algebras 75

References

[1] R. Balbes and A. Horn, Stone lattices, Duke Math J. 37 (1970), 537–546.

[2] J. Berman and W. J. Blok, The Fraser-Horn and Apple properties, Trans. Amer. Math.

Soc. 302 (1987), 427–465.

[3] J. Berman and W. J. Blok, Free Lukasiewicz and hoop residuation algebras, Studia

Logica 77 (2004), 153–180.

[4] J. Berman and W. J. Blok, Algebras deﬁned from ordered sets and the varieties they

generate, manuscript, 2003.

[5] J. Berman and P. Idziak, Counting ﬁnite algebras in the Post varieties, Internat. J.

Algebra Comput. 10 (2000), 323–337.

[6] J. Berman and B. Wolk, Free lattices in some small varieties, Algebra Universalis 10

(1980), 269–289.

[7] G. Birkhoﬀ, On the structure of abstract algebras, Proc. Cambridge Philos. Soc. 31

(1935), 433-454.

[8] S. Burris and H. P. Sanappanavar, A Course in Universal Algebra, Springer-Verlag, New

York, 1981.

[9] A. Diego, Sur les alg`ebres d’Hilbert, Collection de Logique Math´ematique, S´er.A,Fasc.

XXI Gauthier-Villars, Paris; E. Nauwelaerts, Louvain, 1966.

[10] G. A. Fraser and A. Horn, Congruence relations on direct products, Proc. Amer. Math.

Soc. 26 (1970), 390–394.

[11] http://www.cs.elte.hu/~ewkiss/software/uaprog/

[12] G. Gr¨atzer and A. Kisielewicz, A survey of some open problems on p

-sequences and

free spectra of algebras and varieties, in: Universal Algebra and Quasigroup Theory

(A. Romanowska and J.D.H. Smith, eds.), Heldermann Verlag, Berlin, 1992, 57–88.

[13] J. A. Green and D. Rees, On semigroups in which x

= x, Proc. Cambridge Phil. Soc.

58 (1952), 35–40.

[14] F. Guzm´an and C. Lynch, Varieties of positive implicative BCK-algebras—subdirectly

irreducible and free algebras, Math. Japon. 37 (1992), 27–32.

[15] D. Hobby and R. McKenzie, The Structure of Finite Algebras, Amer. Math. Soc., Prov-

idence, 1988.

[16] K. Kaarli and A. F. Pixley, Polynomial Completeness in Algebraic Systems Chapman &

Hall/CRC, Boca Raton, 2001.

[17] H. Lakser, R. Padmanabhan, and C. Platt, Subdirect decomposition of Plonka sums,

Duke Math. J. 39 (1972), 485–488.

76 J. Berman

[18] R. N. McKenzie, G. F. McNulty, and W. F. Taylor, Algebras, Lattices, Varieties,Vol.1,

Wadsworth & Brooks/Cole, Monterey, 1987.

[19] J. Plonka, On free algebras and algebraic decompositions of algebras from some equa-

tional classes deﬁned by regular equations, Algebra Universalis 1 (1971–1972), 261–264.

[20] R. W. Quackenbush, Structure theory for equational classes generated by quasi-primal

algebras, Trans. Amer. Math. Soc. 187 (1974), 127–145.

[21]

A. Szendrei, Clones in Universal Algebra,S´eminaire de Math´ematiques Sup´erieures 99,

Universit´edeMontr´eal, 1986.

[22] R. Wille, Subdirecte Produkte vollst¨andiger Verb¨ande, J. Reine Angew. Math. 283–284

(1976), 53–70.

Completeness of automaton mappings with respect

to equivalence relations

J¨urgen DASSOW

Fakult¨at f¨ur Informatik

Otto-von-Guericke-Universit¨at

PSF 4120, D–39016 Magdeburg

Germany

Dedicated to Gustav Burosch on the occasion of his 65th birthday.

Abstract

In the algebra of sequential functions which map words over ({0, 1})

to words over

{0, 1},wecallasetM complete with respect to an equivalence relation if the subalge-

bra generated by M contains at least one element of any equivalence class. The paper

summarizes the results with respect to some known completeness notions, such as the

classical completeness, τ-completeness and Kleene-completeness which can be reformu-

lated as completenesses with respect to some equivalence relations, and it presents some

new results on completeness with respect to further equivalence relations. Moreover, we

discuss the metric completeness which is nearly related to completeness with respect to

an equivalence relation and can also be formulated in terms of equivalences.

1 Introduction

In the structural theory of automata the following two problems belong to the most important

questions.

• Given an automaton A or an equivalent device, a measure of complexity and some

methods of decomposition, decide whether or not the automaton can be decomposed

into simpler automata.

• Given an automaton A and a set M of automata and some operations to construct new

automata from given ones, decide whether or not A can be built from the elements of

M by means of the operations.

In this paper we discuss a special variant of the second problem. This variant is known

as the completeness problem:

Given two sets F and M of automata or equivalent devices or other descriptions

of certain input-output-behaviours and some operations, decide whether or not

all elements of F can be generated from the elements of M by the operations.

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 77–108.

78 J. Dassow

The most important case occurs when F consists of all automata which are of interest in

this context. We shall restrict ourselves to automata which transform input words over a

cartesian product of {0, 1} into words over {0, 1}. The reason for this is that other cases

can be described by a codiﬁcation and that such automata correspond in a very natural way

to logical nets which are of some importance nowadays, too. The input-output-behaviour of

such automata can be described by sequential functions, and therefore we shall consider an

algebra of sequential functions. The operations are formalizations of the constructions used

for logical nets.

It is well-known that the completeness of this algebra is undecidable, i.e., there is no

algorithm which decides the completeness of a given ﬁnite set. Moreover, the lattice of

subalgebras has a very complicated structure, e.g. the number of maximal subalgebras—which

can be used as a completeness criterion—is at least inﬁnite. Thus one must consider special

cases to obtain better results with respect to the decidability of completeness. One approach

consists of restricting the set of automata which can occur in F and M (e.g. the restriction to

t-stable automata which obtain the same state for all inputs of length ≥ t or the requirement

that M contains all automata which realize a Boolean function lead to decidable cases, see

[25, 23]). Another approach only requires that ”almost all” automata/behaviours/sequential

functions can be generated. Typical examples are t-completeness and Kleene-completeness

where one only requires that, for any automaton, we can generate from M an automaton with

the same input-output-behaviour at the ﬁrst t moments and that, for any regular language R,

there can be obtained at least one automaton which accepts R, respectively. Both concepts

have practical importance since mostly we can only observe the input-output-behaviour at a

limited number of moments, and automata are often used as acceptors.

The latter approaches can be formulated as follows: For any automaton A we require that

we can generate from M one automaton which can be considered as a representative of A.

From the algebraic point of view this leads to equivalence relations and the requirement to

generate at least one element of any equivalence class. The corresponding completeness con-

cept is the central topic of this paper. The notions of “classical” completeness, t-completeness

and Kleene-completeness can be reformulated as completeness with respect to some equiva-

lence relation. Thus the paper contains a summary of important results in those completeness

concepts studied in the seventies and eighties. Moreover, we present some further equiva-

lence relations which are closely related to those associated with the known concepts and the

related results on completeness.

Hitherto equivalence has been deﬁned on the target set of sequential functions. It is

natural to extend it to the power set. Given an equivalence relation on the set of sequential

functions, we say that two sets M and M



are equivalent if, for any function f ∈ M , M



contains a function f



equivalent to f and vice versa. Based on such an equivalence a further

notion of completeness is studied, the so-called metric equivalence, where—intuitively—it is

required that any function can be approximated up to any accuracy.

In this paper we are mostly interested in the decidability of and in criteria for completeness

with respect to some equivalence relations.

We note that our completeness with respect to equivalence relations diﬀers from the

notion studied by Blochina, Kudrjavcev and Burosch in [4] where an equivalence of sets has

been introduced and one is looking for completeness criteria which hold for all sets which are

equivalent.

Completeness of automaton mappings 79

2 The algebra of sequential functions and its completeness

concepts

First we recall some notions and the associated notation used in this paper.

By N we denote the set of positive integers.

An alphabet is a ﬁnite non-empty set. A word p over an alphabet X is a ﬁnite sequence

of elements of X written as p = x

...x

with x

∈ X for 1 ≤ i ≤ n. λ denotes the empty

word. By X

∗

we designate the set of all words over X including the empty word. Moreover,

we set X

= X

∗

\{λ}, i.e., X

is the set of all non-empty words over X. The length of

awordp ∈ X

∗

is the number of elements of X occurring in p and is denoted by |p|.The

concatenation pq of two words p ∈ X

∗

and q ∈ X

∗

is written as the juxtaposition of p and q.

For two sets U ⊆ X

∗

and V ⊆ X

∗

, we deﬁne their product by

UV = {pq | p ∈ U, q ∈ V }.

The powers of a set L are deﬁned by

= L and L

i+1

= L · L

for i ≥ 1.

We then deﬁne the Kleene-closure of L by



i≥1

Let X be an arbitrary set. By id

we denote the function mapping X to X and deﬁned

by id

(x)=x for x ∈ X.IfX is obvious from the context, we only write id.

A function f which maps a cartesian power of {0, 1} into {0, 1} is called a Boolean function.

By non, et, vel and eq we denote the functions which correspond to the logical negation,

conjunction, disjunction and equivalence, respectively. The constant functions which map to

0 and 1 are designated by k

and k

, respectively. Further, we deﬁne the Sheﬀer function sh

by sh(x

)=non(et(x

)).

2.1 The algebra of sequential functions

2.1 Deﬁnition A function F : X

→ Y

is called sequential, if the following conditions are

satisﬁed:

•|F (p)| = |p| for any p ∈ X

• for any word p ∈ X

, there is a function F

such that F (pq)=F (p)F

(q) for any

q ∈ X

• the set {F

| p ∈ X

} is ﬁnite.

Obviously, if F : X

→ Y

is a sequential function and p = x

...x

with x

∈ X for

1 ≤ i ≤ n,thenF (x

...x

)=y

...y

for some y

∈ Y ,1≤ i ≤ n. x

and y

,1≤ i ≤ n,

are called the input and the output at the ith moment, respectively.

80 J. Dassow

2.2 Example We consider the function F : {0, 1}

→{0, 1}

deﬁned by

F (x

...x

)=y

...y

with y



1ifi ≥ 2andx

i−1

= x

=1,

0otherwise.

F has the output 1 at the moment i if and only if the inputs at the moments i −1andi are

1, i.e., if at two moments in succession the inputs are 1, the output is 1, too.

Further, let F



: {0, 1}

→{0, 1}

be the function deﬁned by



...x

)=y

...y

with y

⎧

⎪

⎨

⎪

⎩

1ifi =1andx

=1,

1ifi ≥ 2andx

i−1

= x

=1,

0otherwise.



diﬀers from F only in words of length 1, where F gives the output 0 for all inputs whereas



gives the input as output.

Now assume that p ends with 0, i.e., p ∈{0, 1}

∗

{0},andq = x

...x

is a word of

length m,then

F (pq)=F (p)z

...z

with z



1ifi ≥ 2andx

i−1

= x

=1,

0otherwise.

Thus we have

F (pq)=F (p)F (q)forp ∈{0, 1}

∗

{0}.

Analogously, we can see that

F (pq)=F(p)F



(q)forp ∈{0, 1}

∗

{1}.

This proves that F is a sequential function with



F if p ∈{0, 1}

∗

{0},



if p ∈{0, 1}

∗

{1}.

Let F be a sequential function. Then we have

F (pqr)=F (p)F

(qr)andF (pqr)=F (pq)F

(r)=F(p)F

(q)F

(r)

which proves F

(qr)=F

(q)F

(r). Therefore F

is a sequential function, too.

We now present some devices generating sequential function.

2.3 Deﬁnition A (deterministic ﬁnite) automaton is a quintuple A =(X, Y, Z, z

,δ,γ)

where

• X, Y and Z are ﬁnite non-empty sets of input and output symbols and states, respec-

tively,

• z

∈ Z is the initial state,

• δ : Z ×X → Z and γ : Z ×X → Y are each a function called the transition and output

function, respectively.

Completeness of automaton mappings 81

We extend inductively the functions δ and γ to Z ×X

by setting

∗

(z,a)=δ(z,a)andδ

∗

(z,pa)=δ(δ

∗

(z,p),a)),

∗

(z,a)=γ(z,a)andγ

∗

(z,pa)=γ

∗

(z,p)γ(δ

∗

(z,p),a))

for p ∈ X

and a ∈ X. The function F

: X

→ Y

deﬁned by F

(p)=γ

∗

,p)for

p ∈ X

is called the function induced by A.

If we deﬁne the functions

(q)=γ

∗

(δ

∗

,p),q)forp ∈ X

then we get

(pq)=γ

∗

,pq)=γ

∗

,p)γ

∗

(δ

∗

,p),q)=F

(p)F

(q).

Moreover, there are only ﬁnitely many diﬀerent functions F

since there are only ﬁnitely

many diﬀerent states δ

∗

,p). Thus the function induced by an automaton is a sequential

function.

On the other hand, given a sequential function F : X

→ Y

, we can construct the ﬁnite

automaton

=(X, Y, {F }∪{F

| p ∈ X

},F,δ,γ)

with

δ(G, a)=G

and γ(G, a)=G(a).

It is easy to prove that F (q)=γ

∗

(F, q).

Hence the sets of sequential functions and of functions induced by automata coincide.

2.4 Example We illustrate the above construction of an automaton for a given sequential

function starting with the function F of Example 2.2. With the notation of Example 2.2 we

obtain the automaton

A =({0, 1}, {0, 1}, {F,F



},F,δ,γ)

with the functions δ and γ described by the following tables (the rows correspond to states

and the columns to inputs, and the value is given in the corresponding intersection):

F FF



γ 01

F 00



Logical nets are our second concept to generate sequential functions. We only present an

informal deﬁnition of this device and the associated function.

The basic logical nets are:

and from these elements further logical nets can be constructed using iteratively the following

operations:

82 J. Dassow

where we require that any path from the “input” i to the output contains at least one basic

logical net of type S.

Obviously, any logical net has a certain number n of inputs and one output. Now we

assume that at a certain time moment t the i-th input gets the value x

(t) ∈{0, 1}.Thenwe

associate with the basic logical nets the following functions:

• the output of et at the t-th moment is et(x

(t),x

(t));

• the output of vel at the t-th moment is vel(x

(t),x

(t));

• the output of non at the t-th moment is non(x

(t));

• the output of S at the ﬁrst moment is 1, and

the output of S at the t-th moment is x

(t − 1) for t ≥ 2.

Thus the elements et, vel, and non realize at any moment the corresponding Boolean func-

tions, and S stores the input for one time moment.

Now we extend the associated function in the natural way to arbitrary logical nets.

Thus with any logical net N with n inputs we can associate a function

:({0, 1}

)

→{0, 1}

Obviously, the output at the t-th moment depends on the inputs at the t-th moment and

the values stored at that moment in the elements of type S. If we interpret the tuple of the

values stored in the elements of type S as a state, then the output depends on a state and

the tuple of inputs. An analogous situation holds for the values stored at a certain moment.

Therefore the output and the state at the next moment can be described as transition and

output functions of a ﬁnite automaton. Conversely, if we code the set of inputs and states

by tuples of zeros and ones then the transition and output functions can be interpreted as

Boolean functions which can be realized by logical nets (for details see [11, 18]).

2.5 Example We illustrate the idea by converting the automaton constructed in Exam-

ple 2.4 into a logical net. Since A

has two input symbols and two states, both sets can be

coded by {0, 1}. As the initial state we have to take 1 because the elements of type S have

the output 1 at the ﬁrst moment. Thus F corresponds to 1 and F



to0whichresultsinthe

Boolean functions

δ 01

1 10

1 00