AUTOMATA MANIFOLDS B. I. Plotkin, Ts. E. Dididze, and E. M. Kublanova

UDC 5 12~

Automata manifolds are described in terms of the free semigroup of denumerable rank. At the same time manifolds of other structures, .close to automata, are considered. In particular, manifolds of polygons and of automata with fixed semigroup of input signals are investigated.

1. 1.

AUTOMATA AND STRUCTURES CLOSE TO THEM

By automaton we shall understand a Mealy automaton, i.e., a system 91 = (A, X, Y, 6, ~.), in which A is

the set of states, X the set of input signals, Y the set of output signals, ~ the transition function, and X the output function of the automaton. The function 6: A • X ~ A defines the representation of the set X by transformations of the set A, wlfile the function X: A • X -+ Y associates to each x ~ X a mapping of the set A into the set of output signals Y. We shall agree to write aox-----6(a,x) and a * x = X(a, x) (a E A and x E X).

Here o and * are interpreted

as algebraic operations, while we shall consider the automaton as a tribase algebraic system with respect to these operations and denote it by 91 = (A, X, Y), without stating the basic operations in the notation. In agreement with the general rules, relating to multibase systems, there are defined, for example, subautomata, homomorphisms of auIn particular, the homomorphism ~ : ( A , X, Y)--,-(A', X',Y') q~:A--~A', ~:X--~-X', and cp:Y.-~y; related by the conditions (aoxl~=a~ox ~ and (a,x) ~ = a ~ , x ~.

tomata, and cartesian products of automata.

Here we arrive at the category of all automata. the category of Moore automata.

is the mappings

Together with this category of Mealy automata we consider

An automaton ~1 = (A, X, Y) is a Moore automaton if a certain mapping /~: A -+ Y

is defined, connecting o and * by the condition a * x = (a o x)~.

In the definition of homomorphisms of Moore

automata the condition of permutability with the corresponding /~ is also required. We shall be interested in the manifolds of automata and certain other structures, close to automata. These are first of all polygons. A set A is called a polygon over a semigroup P if for every a E A and 7 E P an element a o ~ E A is defined, where; the condition a o ~0h = (a o 1~) o ~h is satisfied.

In the definition of monoidal polygon over

the monoid P it is also required that a o e = a hold for every a E A (here e is the unity in P).

For every fixed

P we have the category of all P-polygons in which homomorphisms are the mapping of sets that are permutable with the action P. Further, we term action the pair (A, P), consisting of the semigroup P and the P-polygon A.

The homo-

morphism of the action r :(A, P) ~ (B, 2;) is the mapping ~0: A ~ B and the homomorphisms of the semigroups ~o: P ~ Z are related by the condition

(a o 7)w = a ~ o ~ .

Here we have the categories of actions.

It is possible to

discuss separately the category of monoidal actions and the category of group actions. The next object consists of semigroup automata. A semigroup automaton is a tribase system (A, I', Y) in which A and Y are the same as in the automaton and P is a semigroup. It is also assumed that A is a P-polygon with respect to the operation o and an operation * is defined, associating to every a E A and to every 7 E P an element *3', belonging to Y. Aside from this, the operations o and * are related to the identity a,W~=(ao~O*?... The semigroup automaton (A, P, Y) is called a Moore automaton i f P is a monoid and A is a polygon over the monoid P. In tiffs case for every a C A and 7 E P we have a , l ~ a * T e = ( a o ~ l ) * e . In the usual way homomorphisms of semigroup automata are defined, and then the category of semigroup automata arises. It is also possible to speak of the category of P-automata for every fixed semigroup P.

Translated from Kibernetika, No. 1, pp. 47-54, January-February, 1977. Original article submitted August 6, 1974. This material is protected by copyright registered in the name o f Plenum Publishing Corporation, 227 West 17th Street, New York, N.Y. 10011. No part o f this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission o f the publisher. A copy o f this article is available from the publisher for $Z50.

46

To every automaton 91 = (A, X, Y) there corresponds a definite semigroup automaton."

Let F = F(X) be the

free semigroup over the set X. Together with X in A there also acts F; consequently, A is an F-polygon. Let, further, u = u~x, x ~ X, be an element in F and a E A. Putting a , u = ( a o u O * x , we extend the operation * to F. It is easily verified that for arbitrary u I , u 2 E F there holds a , u,u~---(ao ud * u~.

In this case the homomorphisms

of automata induce homomorphisms of the corresponding semigroup automata, and this means that a functor is given from the category of automata to the category of semigroup automata. We now assume that the automaton 9/-----(A, X, 1I) is a Moore automaton with mapping p: A ~ Y.

In tiffs

case in place o f F = F(X) we take the free monoid F* = F*(X), which acts in an obvious way in A, and put a , e = a~, e is the unity in F*. Moore automaton.

The semigroup automaton (A, F*, Y) arises, obviously representing a semigroup

To each semigroup automaton (A, P, Y) there corresponds an action (A, P).

2. Let us make some remarks about free objects in the above categories. If P is a semigroup, then by P* we denote the result of externally joining unity to P. In order to construct the free P-polygon over a certain set Z, we shall proceed in the following way. F o r every z E Z we shall denote by zP* the set o f formal expressions z o 'Z, ?E F*.

By a regular operation this set becomes a F-polygon and, it is easily grasped that this polygon is a

free cyclic polygon with generating element z = z o e.

The free union of all zP* over all z ~ Z gives the free

P-polygon over the set of free generators of Z. We also note that if the semigroup P has a unity, then, repeating the preceding construction with P in place of '-'* , we come to the free object in the category o f monoidal P-polygons. Let there be given a pair o f sets (Z, X). We construct a free action over this pair. We first take the free semigroup F = F(X) and let A be a free F-polygon with set o f free generators of Z. It is easily seen that the action (A, F) satisfies suitable conditions of freedom. We now take the triplet of sets (Z, X, Y1 ) and define over this triplet a free semigroup automaton. first (A, F) be a free action over the pair of sets (Z, X). z E Z and u E F, and let Y = Y~ U Y2-

Let

We denote by Y2 the set of formal expressions z * u,

The semigroup automaton (A, F, Y) arises, which satisfies the necessary

conditions of freedom. And, finally, we note that the automaton (A, X, Y) is free if and only if the semigroup automaton (A, F(X), Y) corresponding to it is tree. Simple considerations show that subautomata of free automata are also free automata. 3. The manifold o f automata consists of classes of automata described by certain identities. Thus, for example, we come to the manifold considering the class of automata with commutative action at the input. It is also possible to define a manifold of automata with commutative action at the output. Various manifolds are defined on the basis of the concept of nilpotency. All o f these classes of automata play an important role in the general theory of automata. The well-known Birkhoff theorem gives an invariant characteristic for manifolds. In automata theory manifolds can be used in the usual way for an algebra of channels. This is primarily a classification of automata according to the criterion o f identity relations that are satisfied in them. Identity relations, just as defining relations, play an important role in the description of automata. Every automaton is a h o m o m o r p h i c original of a suitable free automaton in the manifold generated by the given automaton. Therefore the free automata of various manifolds present essential interest. In certain cases these automata can also be finite. Finally, manifolds correspond to verbal congruencies in individual automata, which can play a substantial role in structural theory, in particular, in problems of automaton decomposition. It is not excIuded that all this may be useful from the viewpoint of technical applications as well. Speaking further about automata, we shall have in mind primarily semigroup automata. The structure of the semigroup ~automaton appears as a natural algebraic structure, particularly if we are concerned with the linearized variant. This means that A and Y are modules over a certain commutative ring and both representatives o f the semigroup P (connected with the operations o and . ) are linear representations. Finally, a more general case may be considered, where A and Y are ~2-algebras with respect to a certain system of operations ~2, belonging to a certain manifold of fZ-algebras. In passing we note that for semigroup automata the operation of splicing is defined naturally. Let ~Ii = (A,, r~, YO and 9/~ = (A~, r,,y~) be two such automata. Their splice 91 = 91~wrPI~= (A, P, Y) is defined in the following way.

A is the cartesian product At•

Y = Y~ • Y~, 1" is the splice of the semigroups P 1 and F 2 over the

47

set A 2 : I" ----rla'xF2. (ajo/~ (a~), a~ o 72)

If, further, (f, 72) E r (f is the mapping of A2 into F1), (a l, a2) E A, then we put (ai, a,) o (~, ~ ) =

and (a~, a , ) , (f, V,) = (ai * [ (a2), a, * ~,).

It can be directly verified that here indeed a semigroup

automaton appears, and it is easily grasped that the splice of Moore automata is a Moore automaton. of splicing semigroup automata is closely connected with cascade connection of automata.

The operation

According to the Birkhoff theorem manifolds occur in a one-to-one correspondence with 'the totally characteristic congruencies o f suitable free objects. The general principle established in this theorem covering manifolds i n various concrete situations is completed by the investigation of the corresponding totally characteristic congruencies, and this adds new content to the general connection. Such an investigation is carried out for automata in the usual terms for transformation semigroups, and the final characteristic o f automata manifolds is based on the language of free semigroups o f denumerable rank. In the course of the investigation manifolds of other systems, close to automata, are also considered. The present article is divided into two parts. description is given of polygon manifolds.

2.

In the first part, along with the preliminary information, a

MULTIBASE SYSTEMS

1. Let us define the basic concepts relating to manifolds of algebraic systems (cf. [2]), which will be applied to the special cases considered by us. The multibase system 9i-~ (Al, A ~ , . . . , A~)

is defined on certain k base sets Ai, i = 1, 2, ..., k.

~2 of algebraic operations, defined on 9/, is a system, in general, of multibase operations: operation is n-ary, then a~a,...a,~oJ

E g2 and this

is an element in a definite Aj and the arguments a~, a s , . . . , a ~

specialized in the base sets Ai.: a i E A t i . given base set A~.

If r

The system

are also

Certain operations of the system ~2 can also be monobase, relating to a

The corresponding rules of specialization are stated in the characterization of each co.

Mono-

typicality of two multibase systems is defined in an obvious way and thus it is possible to speak of ~2-systems with given set of operations fL The homomorphism q~: 9/--~9/' of two ~2-systems is the k mappings qh:A, ~ A',, in a natural sense permutable with all operations of the set ~2.

We shall denote all the ~

by the same letter ~0:

If a i ~ Ati, then a~t ' = a~.

The product of homomorphisms is realized by individual components and one can speak of the category of ~2-systems. In a natural way the homomorphisms, epimorphisms, and isomorphisms of ~2-systems are defined. Let, further, 9.1 = (Ai, A, . . . . . equivalence on the set A i.

Au)

be a certain ~2-system and p----(9i, P~. . . . . 9a) a sequence in which Pi is the

If a and a' are two elements in Ai., we shall write

a0ra' for ap,a'.

The sequence p

is called a congruence o f the system ~I, if this sequence is matched with all the operations of the set ~2.

As usual,

the condition of matching, say with n-ary operation co E fZ,signifies that from a~pa~,...,a,~pa, there foilows a ~ . . . a~o~pa~ . . . aj~o.

I f 0-----(0t . . . . . O~) is a congruence of system ~ ,

92/o=(AJ9~ . . . . . Ah/9~).

then it is possible to pass to the factor-system

A theorem about homomorphisms is formulated in the usual way. The congruence P=(P~,--o

9h) is called totally characteristic if it is invariant wit~ regard to the endomorphisms (isomorphisms h~to itself) of the system ~[.

Tl~is means that for any endomorphism ~

there holds ~a'=~a~-pa "~.

The intersection of congruences

is defined componentwise and it is easily seen that the intersecti:on of totally characteristic congruences of a given system ~

is also a totally characteristic congruence.

if always A[ < ~

The system 9 / ' = (A~. . . . . A~) is a subsystem in 9 / = (eli,. .... Aa),

and the identity embedding 9.I'-+9/ is a homomorphism.

This also means that the corresponding

conditions of closure with respect to the operations also hold. The intersection of subsystems is defined componentwise. If X = (X~ . . . . . Xk) is the set of sets with X~ ~ A~, i = 1, 2 . . . . . te, then it is possible to speak of the intersection of subsystems, containing X.

This will be the subsystem generated by the set X.

Let there be given a set of ~2-systems 92~ = (A~'. . . . , A~). The system ~[ = (A~. . . . . A~) is the cartesian product of all 9/% if A i. is the cartesian product of the sets A~, i = 1, 2, ..., k, and all operations in nentwise in terms of the operations in each 92~ .

9/ are defined compo-

In the usual way we define homomorphisms of projection and

verify that the cartesian products satisfy the universal property of direct products in the category, of all ~2-systems. This property of cartesian products allows us to prove the Reymach theorem for ~2-systems: If P~, ~ ~ [, is a set of congruences of the ~2-system 92 , then the factor-system 9 2 / f ) ~ product of all ')1/9~ 9

48

admits a natural embedding in the cartesian

Automata, semigroup automata, and actions are all examples of multibase algebraic systems, and all o f the above definitions are applicable t o these special cases. 2. The class .~' of g~-systems is called closed if this class is closed with respect to taking homomorphic originals, subsystems, and with respect to cartesian products. We shall show that in every closed class of ~-systems there exist free objects. We shall first do this for the class of all ~2-systems. Let w ~ r

and let this operation be n-ary.

We term the type o f this operation the sequence (i~, ..., i~, i),

showing that the s-th argument in the application o f r the result of applying co is contained in Ai.

must belong to the set A~ o f the given system 9/, while

If co is nullary, then its type i shows that co determines a definite

element in the set A~. Let, further, ) ~ = (X~. . . . . Xh) be a set of k sets.

We call the elements in ~

term words of type i all nullary operations in ~2 of type i. type (q . . . . .

i~,i) and w ~ , w 2 , . . . , w , ~

are words of type

Further, by induction,

~,i~ .....

words of type i.

We also

if co is an n-ary operation o f

i,~, respectively, then w t ... wnw is a word of

Wpe i. Denoting by Wi the set of all words of type i, we come to the ~2-system W= (Wl, ..., Wk)with here a natural application o f the operation of the set g2.

This system is obviously freely generated by the set X'= (X~, ..., Xk).

We now take an arbitrary closed class of ~2-algebras ~ and consider in W all possible congruences p~ for which W / p - , ~ .

I f p =~1 P--~, then by the Reymach theorem W / p ~

free in ~ over the given set of sets X.

and it is easily grasted that tlfis a - s y s t e m is

The freeness condition here, as usual, signifies that if 9.1 = (A~. . . . . A~) ~

and there exists a set of mappings % : X ~ - + A ~ , i =

k , then all these mappings are uniquely continued up to

1, 2 , . ,

the homomorphism q~: W / p -+ 9/. 3.

Let us fix a certain closed class of ~2-systems K.

We denote by 11o the free system in K generated by

the set X = (X 1 . . . . . Xk) with denumerable Xi, i = 1, 2 . . . . , k. Let us take an arbitrarY subclass $ (p~. . . . . P~.), defined b y

the following rule.

We put 110= (V~ . . . . .

in K and associate to it in the free algebra 110 the congruence p = I f u and u' belong to Vi, then upiu' on condition that for every

homomorphism qo:lIs 9/ with 9IE~ there holds u~ = u '~ . 110 and that this congruence is totally characteristic.

A simple test show-s that p is in fact a congruence in

Let, on the other hand, Pi be a certain binary relation on V i. we associate the subclass ~ in K.

Vk).

We put 9 / = (A~. . . . . A~) E ~, if from

every homomorphism (p : lI0 --,-. 9/ there holds u~ = u~~ . . . . . test shows that ~ is a closed class.

u~ = u'~~.

Consider the set p = (P~. . . . . Ph), to which u~p~ul, u~p~u'~ . . . . , Ukpku"k it follows that for

Here ~ is given by identities, and an obvious

In the Birkhoff theorem it is stated that this established a one-to-one correspondence between closed classes in K and the totally characteristic congruences of the free object 9/o, and it is shown that the closed classes are nothing else than manifolds, i.e., classes given by identities. This theorem is proved literally in the same way as the standard monobase theorem. Let us repeat the corresponding considerations. Let p = (P~,..., 94) be a totally characteristic congruence in 110- Let to this congruence there correspond the class ~ and let ~ correspond in go to the congruence p ' = (P~. . . . . P;).

We have 9-~ p-~, where the inclusion is

understood componentwise. Noting that the system lI0/p belongs to ~ , and using the natural homomorphism l I 0 - + l I J p , we obtain the reverse inclusion. Let now 3~ be a closed class in K.

Let to this ~ in 110 there correspond the congruence p = (P~. . . . . Pa)~ and

let ~' be a manifold defined by this congruence.

We have ~ ' .

It is necessary to estabfish the reverse inclusion. n

Let 11- be an arbitrary free system in K. the intersection o f all ~

To the class 3J we associate in 1I the congruence 7, coinciding w i t h

for which 1 I / ~ E ~ 9 It is to be understood that Ilt~E ~ and ff = It/~ is a free system in ~.

49

Let us take 9I E ~ ' .

We select the free system 1I for which there exists the epimorphism 1I--~ ,~.

definitions it can be derived that the kernel of this epimorphism contains the above-defined congruence ~?.

From the Con-

sequently, there also exists the epimorphism I~-~-X and 9~, together with the left member, belongs to 2~. This completes tile proof of Birkhoft~s theorem. In addition we note that the identities considered here in the multibase case are polyidentities - they are concerned with several sorts of variables.

3. t.

MANIFOLDS OF POLYGONS

The consideration of mangfotds o f poIygons is the first step to the characterization o f manifolds of au-

tomata. If F is a semlgroup and A a P-polygon, then A may be considered as an algebra (monobase) in which the elements in F are interpreted as unate algebraic operations. All possible F-polygons constitute a manifold in the class of all such F-algebras. Tile manifolds of P-polygons are submanifolds in the manifold of all P-polygons. In the category of all F-polygons there obviously exist direct and free products. The role of direct products is played by cartesian products, while the role of free products is played by free unions of polygons. Not every manifold of P-polygons is closed with respect to free unions. We determine the manifolds satisfying the additional condition of closure over free unions. We call such manifolds special and interest ourselves in the characterization of special manifolds of P-polygons. We ftrst present a general consideration. If P is a semigroup, then by P(P) we denote the category - the manifold of all P-polygons. When P has a unity, we determine further the category P*(F), corresponding to the monoidal F-polygons, where unity acts as the unity transformation. It is also to be understood that P*(P) is a submanifold in P(F). We recall that by F * we denote the result of joining unity to P externally. We shall show that between the manifolds in P(P) and the manifolds in P*(P*) there is a natural one-to-one correspondence. If A is a P-polygon, then A is at the same time a P*-polygon: The new unity acts in A as a unity transformation. Considering A as a P*-polygon, we shall denote it by A*. All these A* are objects in P*(F*). Let now be a certain class of P-polygons. We denote by ~* the class of all A* over all A E 3 . It is to be understood that 3" is a class in P*(F*) and that the correspondence ~ - - ~ * is one-to-one. It is also obvious that J~ is a manifold if and only if 3" is a manifold and that to special manifolds there correspond special manifolds. All of this means that in tile description of manifolds of P-po[ygor~s it is possible to limit consideration to the case where P has a unity and we are concerned with manifolds in P*(P). We shall now assume this situation. gons in P*(F).

Let us fix a certain monoid P, and let ~

We term kernel of this class in P the binary relation 9 = 9 ( 3 ) ,

be a certain class of P-poly-

defined by the rule 71#~/2, if the

identity xoT~ = xo'h is satisfied in every polygon in ~ . It is to be understood that a kernel is always a congruence in P, which coincides with the intersection of kernels of the representations, corresponding to all possible polygons in 3 . Let, on the other hand, p be a certain binary relation on P.

We associate to it the class ~ in P*(P) by the rule

A E 3, if the identity xo,h = xos'~ is satisfied in A if only 71 P"12. Obviously, here 3 is a special manifold. THEOREM 1.

Special manifolds of F-polygons and the semigroup P occur in one-to-one correspondence.

The proof of this theorem will be carried out its kernel in F, and let t~' be a class defined by the necessary to establish the reverse inclusion. We start and a E A. We continue the mapping e -+ a up to Here "hp(a)?~ is equivalent to ao?~-ao?2 a n d p ( a ) i s

by the well-known scheme. Let ~ be a special manifold, ~0 relation p. It is to be understood that ~ ( ~ ' , and it is from the free F-polygon P with free generatrix e. Let A E3 the homomorpkism of P-polygons g: P -~ A. Let p(a) = Ker p. ~ right congruence in P. We have the F-polygon P/p(a). It is

obvious that the kernel r / p (a) fi ~ is the intersection of all possible such p = 9 (.~) and, applying the Reymach theorem, we conclude that the P-polygon F[p belongs to the class 2 ~ . We now take in 3 ~ an arbitrary cyclic polygon A = a o P . g: P -~ A and let p(a) : Ker #.

Comparing e ~ a, we come to the endomorphism

From the definition of the class 3' it follows that we have p ( O (a),

Therefore A

is the homomorphic original of the polygon P/o and together with Pip the polygon A belongs to the class s We now let A be an arbitrary polygon bx ~ ' . We denote by A' the free union of all cyclic subpolygons in A. Since these cyclic terms lie in

3 and 3

is a special manifold, we have A' ~ .

of the polygon A' and, consequently A E 3 .

50

The polygon A is a homomorphic original

This establishes the equality ~ ' = 2g.

Let now ~ be a congruence in P, ~ a special manifold corresponding to this conguence, p' the kernel of the class ~ in PEP. By definition there follows O ~ O ' . To verify the reverse inclusion, we pass to the factorPolygon P/p.

We have "hP3h ~ (x~h)p (x~)=~xo~h = x o ~ , x is an arbitrary element in P/p.

This means that r / 0 r

We take ~ip'Y2 and let e be the unity in PEP. We have (~o~h)p(eoY~), which implies 3,1P72. ~'

9

Thus we obtain

C.O- Q.E.D.

Let us make several remarks with respect to the special manifolds of general form: P does not necessarily have a unity and a~ does n o t necessarily lie in P*(P). Every such a~ is defined by a certain congruence in PEP*. Let p be such a congruence and [e] its coset, containing the external unity e.

All o f the other cosets lie entirely

in PEP, and if further e is eliminated from [e], we obtain a congruence in PEP wlfich we denote by /9', a kernel of the class ~ in PEP. Furthermore, the set [e]N.e can be characterized as a centralizer o f the class all 3, ~ P for which in the polygons o f

a~ the identity xo~g= x holds.

a~ in PEP; it consists of

It is not excluded that the centralizer of a

class is empty, and if so, then it coincides with one of the cosets of the kernel o f the initial a~. Tlzis remark also signifies that every special manifold of P-polygons can be given by identities of the form xoyl = x~ and xo~ ----x, 3'i, '~, ~' E I'. 2.

Consider arbitrary not necessarily special manifolds of P-polygons.

Let a semigroup P be fixed and let ~ be a certain class of P-polygons. sider in PEP also the annihilator U, defined in the following way. of ~ the identities xoy =yo~, hold.

Together with its kernel p we con-

U consists of all 3" r I" for which in the polygons

In other words, 3' r U, if for every

A~

all of the elements in A are trans-

lated by the transformation 3, to the same element of A, in general, dependent on 3,.

The annihilator of a class is

always a two-sided ideal in PEP and, furthermore, it is directly verified that it is connected with the kernel p by the following conditions: 1)

U is the union o f certain residue classes of the congruence p;

2)

every residue class o f the congruence p, belonging to U, if a left ideal in I'.

We shall also say that a certain ideal U and equivalence p of the semigroup P composes in it a matched pair if for them the two conditions noted above are satisfied. Thus to every s there corresponds a matched pair (p, U), consisting of the kernel and annihilator to the class ~ in PEP. Let now U be an arbitrary subset and p an arbitrary binary relation in PEP. We associate to the pair (p, U) the class of polygons s by the rule A E .~ and identities x oy~ ~ xoy~ if 7~ P72.

if, in A, identities of the form xoy -----yogi are satisfied for all 3' E U

It is to be understood that s is a manifold and that this manifold is not special

if U is not empty. THEOREM 2. If P has a unity, then the connection considered here between the classes and pairs of the type (p, U) gives a one-to-one correspondence between the manifolds in P*(P) and matched pairs (p, U) in the ideal U and the congruence p in PEP. Proof. We shaI1 first establish the connection between tlm matched pairs of the w p e (p, LO and the totally characteristic congruences of free polygons, and then use Birkhoff's theorem. Let PEP be a s e m i g o u p with unity; Z is an arbitrary set, containing not more than two elements; A is a free PEPpolygon over Z in the category P*(P). gruence p.

a=z~oy~

Let, further, (p, U) be ,x,a matched pair in PEP of the ideal U and the con-

We define according to this pair a binary relation p

and b=z~oy~.

on the set A.

Let a and b be elements in A,

We put a~b if z 1 = z 2, 3,1/)3,2 or z i ~ z ~ , YIPY~ and 71, 3,2 belong to U.

We shall show

that p is a totaily charactei4_'stic congruence of the polygon A. Reflexivity and symmetry o f the relation p are obvious. Let us verify transitivity. We have 7iP~207a,

Let a~b & b~c, a = z~oyi, b =

then we already have apc. If z
If z~ = z 2 = z s ,

31

zl = z~ = z and z~--- z'o~? , then

z~oy~= z ' o y y l , z~o~,~= z ' o T ~ and from (771)P(73'a) there follows (z~Coyi)'p(~y~)o

Let now z~ ~ z ~ , ~ = zlo~i,and ~ = z~o~.

We have ~ o~h = zlog~'h and ~o"h = z~o,/~"h .

Furthermore, since 71 and

7a belong to U, then with regard to the matching conditions we obtain (?i'h)9?iP~?~P ("h~'~) and hence are elements in U. "kt"

Together with

('el'h)P (~?~'%)this gives (~~176

.

"fi?~ and ~s

T h b establishes the required properties of

P. 'k,

Let us pass to the factor-polygon A =

AlP.

Let p'~ be its kernel, and U' the annihilator in P.

We shall

show that p' = p and U' = U. Let "r E U, a and be arbitrary elements in

A, a -- zi o ~h, b -- z~ o ~h.

Here 7t?, "bY belong to U and (7t~?)9(~&7). Consequently, (apT)9(bo?). lator U'.

(z~o?)O(z~o3?); but this is equivalent

If, on the other hand, 7 E U', then for z l, z 2 E Z we must have

to 3' E U.

Thus, U' = U.

Assume that ~1P3"2 is true. Here ('r3'x)P(73'a), whence r

Then a o ? = zi o ~,~7 and b o ? = z~ o ?~'f. This means that 7 belongs to the annihi-

,

~h972, then

for

We take an arbitrary

(ao'h)~(ao'~2).

a=zo'~EA.

Then

ao~h=zov,~i and aoy~.=zo~,?~.

Thus, 71 and 72 act identically in X and ?tp'~,~.

If we start from

(zo'h)p(zoT~.), and this means that 71P% is satisfied.

z E Z we will have

This verifies the

equality p = p'. We take in the P-polygon A an arbitrary totally characteristic congruence r2. and # be the kernel of the polygon A in P.

Let ~. =

A/~, U be an annihilator,

By the matched pair (p, U) we construct the corresponding p .

We shall

show that ~7 = P . Let

a'ffb, a-=z~o,~ and b-----z~o?~. If z~ = za = z, then 3qP72 and since p is the kernel of the polygon (z~o,h)aq(z~o?~)~l(Z2o'h),

A/~, we have (zo,h)~l(zo~h) and a~Tb. I f z I ~:Za, then 71 and 72 are in U, 71P3'a and hence

a~b. This verifies the inclusion o ~ 1 Now we shall start from

-

a~lb, a=z~o'h, b=z~o'~2.

Let first z 1 = z a = z.

a r b i t r a r y c and considering the total characteristicness of ~, we have hence,

(co~h)~l(co'%).

Substituting in place of z an This means that 7~PTa and,

ap b. Let now zl ~ z a.

for arbitrary ci and ca .

We put for z I and z a arbitrary cl and c~.

Then(z~o?d~l(z~o~&) hnplies (c~o?dTl(c~o?3)

Consequently, for arbitrary c~ and c a in A we have

c~ o ?~ ----c~ o "h, ~ E U , and ~'~p3~2. This means that (z~ o ?t) 9 (z~ o ?~), apb holds.

c~o3h=c~~

Hence c~o~----

Thus, p = ~.

From these constructions it follows that the totally characteristic congruences of free P-polygons unuer consideration can be completely reduced to the corresponding matched pairs of the type (p, U) in P. The theorem now follows from the Birkhoff theorem and the following remarks. First of al! we note that if (p, U) is a matched pair ira P and p

is the corr~ponding congruence in A, say

for denumerable Z, then the manifold of P-polygons ~g, defined by the congruence p , coincides with the manifotd defined by the pair (p, U) by the rule stated before the theorem.

This follows directly by constntction.

Let, further, ~ be a manifold of P-polygons, the set Z be denumerable, r~ the congruence of the manifold 3~ in the free polygon A, and (p, U) the kernel and annihilator of ~

in P.

Then (p, U) is the kernel and annihilator

of the polygon X = A/r/. Indeed, let

(9',U') be a kernel and annihilator of the polygon A.

Since AE3~ , then 9 ~ 9' and

U ~ U'. To

verify the reverse inclusions, it must be shown that in every B E~ the identities b o'~ = b o?~, if 7~P'Ta, and b ~ o ? = b~o?, if 7 ' E U , are satisfied, respectively. It is sufficient to consider the case where B has two generatrices, tn this case the endomorphism r -+ B holds, from whose existence it follows that the kernel and annihilator of belong to the kernel and annihilator, respectively, of B. This means that the above identities are satisfied in B. have the reverse inclusion. Q.E.D.

52

We

To complete the investigation it is necessary to consider the case where 3~ is not necessarily a manifold in P*(P) and F may not have a unity. F r o m the above reduction it follows that in this general case the case ~ must not only be associated with a kernel # and an annihilator U, but also a centralizer, which we shall denote by V. The manifold 3.

~ is given by identities of the form xo"h ~ x o ? ~ with ?~p?2, x o ? - = y o ? w i t h ~ ? E U

Let us make some additio:~al c o m m e ' t s .

andxoT=xwith?EV.

Let P be a semigroup, U a two-sided ideal in it.

by p the Riesz congruence in F, defined by the ideal U.

We denote

It is understandable that here the matched pair (#, U)

arises. The manifold of polygons, defined by this pair, consists o f all those P-polygons A in which all elements in U carry every a E A into a certain % . Let, on the other hand, p be an arbitrary congruence in P. We consider all possible residue classes of the congruence p, representing left ideals in P, and let U be the union of all these classes. Here u ~ U is equivalent to satisfaction of 7 E P for arbitrary (Tu)pu.

If now u E U and o is arbitrary, t h e n ( T u ) p u implies 7(uo)p (uo) and,

consequently, U is a two-sided ideal in P, matched with p, and is the greatest in this sense. p is the empty ideal. We denote by ~

the manifold of F-polygons, defined by a certain matched (#, U), and let ~0 be a special

manifold with the same # (an empty U). polygon in ~0 also lies in f t .

It is understandable that /~ ~ ~o.

We shall show that every cyclic P-

Let A be such a polygon, and let this A be generated by the element a. has the form b ~ a o ? , ? E r . identity x o u = 9 ~ u holds.

The least ideal matched with

Let u E U. Then ('yu) pu and a o ~ u = a o u . This gives the inclusion A E ~.

Every b E A different 2"rom a

Hence b o u = a o u

and in A the

Consider the case where P is a group and we are connected with the manifolds of group P-polygons. If is such a manifCd, then its centralizer is a normal divisor of V, while the kernel p coincides with the congruence defined by this normal divisor. Here it is already possible not to speak separ,~ely of V and #, but it is only necessary t,~ speak of the kernel V. It is also understandable that if the annihilator U is not empty, then ~ consists only o f siagle-element polygons. Thus all manifolds different from the trivial manifold consisting of singleelement polygons, are special manifold,;. Let now find its :r

3~ be a manifold of group P-polygons, and V its kernel in P.

configuration for tile manifold .~.

For an arbitrary P-polygon A we

This congruence coincides with the i-ltersection o f all such ~ in

A for which in A/~7 the elements o f V act as unity. It is easily grasped that this intersection coincides with the partitioni:ag of the polygon over orbits of the normal divisor V.

LITERATURE CITED 1. 2. 3. 4.

V . M . Glushkov, "Abstract theory of automata," Usp. Mat. Nauk, 16, No. 5 (I01) (1961). J. ttiggins, "Algebras with a scheme of operators," Math. Nachr., 27, Nos. 1, 2 (1963). B . I . Plotkin, Automorphism Groups of Algebraic Systems [in Russian], Nauka, Moscow (1966). Ts. E. Dididze, "On homomorphism of automata," in: Questions of Computational Mathematics, Transactions of the Computer Center o f the Academy of Sciences of the Georgian SSR [in Russian], Vol. 12, No. 1, Tbilisi (1973).

53