Notion de demi-bande demi-bandes de type deux

Semigroup Forum Vol. 10 (1975), 115-128

NOTION DE DEMI-BANI~

DEMI-BANVES DE TYPE DEUX

Benzaken C. et Mayr H.C.

SUMMARY

In semigroup theory, the notion of semiband which generalises

that of band, may play an interesting role both in pure alg~ebrafc

theory and in computing and programming theory.

A relatively complete study of the structure of sen/band of

type two is given together with a complete listing of their isomor-

phism class.

We are much indebted to G.J. Lallement for suggesting improve-

ments in our presentation and for connmnicating his computations

concerning semibands of type two.

115 © 1975 by Springer-Vedag New York Inc.

C. BENZAKEN, H.C. MAYR

I- INTRODUCTION

Nous savons [~] que la structure ou l'architecture d'un demi-

groupe fini est un compromis entre celle de groupe et celle de demi-

groupe ccmbinatoire ; en cons@quence, ni l'ume ni l'autre ne peut

assumer seule les qualit@s d'un demi-groupe. La notion de demi-bande,

c'est ~ dire de demi-groupe engendz@ par des ide~tents, peut jouer

ce rSle (Th@or~me 2). On en trouve d@j~ une @tude approfondie dans

I;3]. C'est par l'infonmatique, en fait, que les auteurs se sont in-

t@ress@s aux demi-bandes.

- En effet les machines ou automates s@quentiels finis

qu'on envisage avec faveur, sont asynchrones (ce qui permet une plus

grande sGret@ en @vitant certains al@as). Psrmi eux, il y a ceux pour

lesquels, pour chaque entr@e x et chaque @tat interne q, l'@tat suc-

cesseur (qu'on note qx) v@rifie

(qx)x : qx.

Cela signifie que le mono~de de transition d'un tel automate est une

demi-bande finie.

- Plus g@n@ralement, si l'on d@finit un calcul come une

suite finie de configurations co~amd@es par une suite d'actions @l@-

mentaires A, B, ..., (urn programme), il arrive souvent que la r@p@ti-

tion d'une action @l@mentaire me modifie pas la configuration en

tours.

C'est le cas lorsque par exe~p!e les actions @l@mentaires sont

du seul type affectation si~ole a :: b (cf. [2]), ou plus g@n@rale-

ment du type affectation a := f(xl,x2,...,x n) non boucl@e (c'est

dire a # x i) et sans effets de bord (sur les x i en particulier).

Dams ce cas, le programme AA est @quivalent ~ Aet le monofde

de transition des configurations est une demi-bande (en g@n@ral in-

finie).

La propri@t@ d't~iversalit@ des demi-bandes, obtenue par le

th~or~me 2, laisse ~ penser qu'il peut en @tre de m@me pour certaines

formalisations d'algorithme ~ instructions @l~mentaires "inutilement

r~p@titives". Ces for~nalisatioDa (restant ~ d~finir) pourraient @tre

utiles dans le calcul parall~le.

116


II - GENERALITES SUR IES DEMI-BANDES

Nous utiliserons les notations de [1]. Nous noterons E M l'en-

semble des idempotents d'un demi-groupe M.

Nous dirons enfin qu'un demi-groupe M est de torsion lorsque

tout sous demi-groupe monog~ne de M est fini ce qui est @quivalent

: tout @l@ment x de M engendre un (unique) ide~ootent e k x

(e x : x k > I).

Nous noterons IXI le cardinal de l'ensemble X.

DEFINITIONS :

- On appelle demi-bande tout demi-groupe ayant tun syst~me g@n@-

rateur ide~potent.

- Sin d@si~e un cardinal non nul, on parlera de demi-bande de

type n, !orsqu'un syst~me $@n@rateur idempotent minimal a pour car-

dinal n.

La classe des demi-bandes est @vider~nent ferm6e par quotient et

par produit cart@sien (fini). Elle n'est pas ferm~e par contre par

passage au sous demi-groupe.

La derni~re remarque apparemment n@gative est co~pens@e par la

propri@t@ universelle illustr@e par le th@or~me I suivant et sa g@-

n@ralisation (Tn@or~me 2).

THEOREME I : Tout groupe G est isomor~he ~ un sous demi-groupe d'une

demi-bande co~ol@tement simple.

On construit un demi-groupe de Rees M = J x G × I de matrice

sandwich P de telle sorte que les Pij (ieI-{io}' J~J-{Jo I) consti-

tuent ume famille g@n@ratrice de G (relativement ~ sa structure de

demi-groupe !) (i ° et Jo sont des indices particuliers respective-

ment de I et J) et o~ Pio j = pij ° 1 (l'@l@ment neutre de G) pour

tout iet j de Iet J respectivement. On rappelle que dons un tel

demi-groupe le produit (j,g,i) (k,g',£) vaut (j,g Pik g"£)"

I1 est clair que la famille d'idempotents

fi : (Jo ,I,i) i~ I-{io}

ej : (j,l,i O) j 6J-{jo}

117


engendre bien ~4 qui centient, entre autres, le sous demi-groupe

{jo} × G × {io} isomo~he ~ G. c.q.f.d.

~MAF~UE : Ce th6ord~me nous donne ume limite du type de demi-bande

cor~ol6tement simple dans laquelle peut @tre plong~ un groupe. Par

exemple un groupe engendr~ (dans sa structure de demi-groupe l) par

q g~n@rateurs pourra @tre plon~ dans une demi-bande de type

min{nl+n21nln 2 >_ q, n~EN, n26N }.

En particulier un groupe monog~ne (fir/ seulement) peut ~tre

plon~ dans une demi-bande de type deux.

Nous devons ~ J.F. Perrot [6] la d~monstration @]%gante du

th@or@me plus g~n@ral suivant :

THEOEE~E 2 : Tout demi-groupe M est isomorphe "_a un sous demi-~roupe

d'une demi-bande T.

Soit gi (i~I) une pattie g~n@ratrice de M. Faisons op~rer fid~-

lement ~ droite M dans X (cela est tou~ours possible avec X = M* et

le produit ordinaire). Soit X' un ensemble en bijection avec X dis-

joint de X (la bijection est not@e x + x'). Posons Z = X~X'.

Dsns Z z les applications

e : Z + Z d@finie par (z)e : x lorsque z = x ou z = x'

(i~I) ~ : Z + Z d~finie par (x')¢i = x'

(x)¢ i = (xgi),

sont ide~0otentes et engendrent une demi-bande T qui contient le

sous demi-groupe M engendr~ par {Yi : e ¢i C [i~I}. Or le calcul

donne

(x)y i = (x')Yi = xg i pour tout x%X

d'oG l'on tire ais@ment l'isono~hisme entre Met M (Yi @tant le

prolongement par "syr~trie" de gi ) .

Ii est int~ressant d'examiner en quoi une demi-bande peut dif-

f@rer d'un demi-groupe idempotent et quelle est la (les) plus petite

qui en diff~re.

PBOPOSITION _I : S_~i Test une demi-bande, n~ idempotente; d_ee torsion

alor~ ~ a au moins trois ~l@ments.

En dehors du cas absurde trivial I~ I = I, la seule possibilit@

118


pour contredire ce fait viendrait du cas F~f : {a,b} a ~ b.

L'idempotent eab vaut alors a (ou b) ce qui entrafne ab : a (ou b) ;

de re@me ba vaut a ou b. Conw~ Test engendr@ par E T il en r@sulte-

rait T = E T contredisant le fait que Test non idempotente.

CONSEQUENCE : ~he demi-bande, non ider~otente , a au moins quatre @l@-

ments distincts.

Nous pouvons m@me pr@ciser :

PROPOSITION 2 : II existe, ~ un isomor~hisme pros, une et une seule

demi-bande non idempotente _~ quatre @l@ments. Elle est de type deux

e_~t poss~de un @l@ment absorbant.

L'existence est assur@e par la demi-bande T 4 pr@sent@e par

<a,b ; a 2 = a, b ~= b, (ab) 2 = ba>.

(On en d@duit en effet aba = bab = ba et doric T 4 = {a,b,ab,ba} et

ba est absorbant).

Montrons l'unicit@. T ayant quatre @l@ments, poss~de au moins

deux g@n@rateurs idempotents a et b. D'apr~s la proposition I,T a

un iden~0otent de plus et un @l@ment non ider~otent. Siab : a alors

(ba) 2 : ba et (bah) ~ = bab. T est alors idempotente (~ 4 @l@ments

au plus). De re@me dams l'un des cas ab = b, ba = a, ba = b ou

ba = ab.

Par cons@quent, T = {a,b,ab,ba} avec par exemple ab non ide~oo-

tent et ba ide~potent. Chacune des hypotheses aba = a ou aba = b

ou aba = ab ir~plique (en multipliant ~ gauche par a et ~ droite par

b) (ab) 2 = ab ; contradiction. Donc aba = ba.

Pour les n~mes raisons bab = ba. D'o~ (ab) 2 : ba et Test iso-

morphe ~ T 4 .

119

C. ~MZAKHN, H.C. ~AYR

III - ~ DES [EMI-BANDES DE TYPE DEUX

III-1 - EEMI-BANIE LIB~ DE TYPE DEUX

Notons L la demi-bande libre (de type deux) engendr~e par

D = dl,d 2 (d I ~ d2). L peut @ire d@finie (~ isomorphisme pr@s)

eonme quotient du demi-groupe libr~ D + (sans neutre) par la congruence

engendr@e par les relations

%% d I d2% d 2

Lest en fair !e produit !ibre de deux demi-groupes ~ un @l@-

ment. Les @l@ments de L peuvent canoniquement @tre eon~id@r@s comte

des roots sur dl, ~ o~ alternent d Iet ~. Donc

L = { d 1,d 2, dld 2 ,~d I ,dld2dl ,d2dld 2 , ...... }

avec comae r@gle du produit

(~di). [~din si i = j

Nous parlerons de la !on~eur d'un ~ot a de L (not@e lla [])

comae le nembre de lettres de a.

PBoPRrETES DE L

- E L : {dl,a 2}

- Lest union disjoints de 6 sous demi-groupes

{dl} I {d2} I ~11 1 ~22 1 L12 1 L21

oG Lij est l'ensemble des mots de L commengant ~ di, terminant ~ dj

et de longaeur su~rieure ~ un. Ces 6 sous demi-groupes sont mono-

g~nes et les 4 derniers sont librement engendr~s respectivement par

THEOF~ME 5

(a) La seule demi-bande infinie de t~e deux (~_ isomor~hisme

pros) est la demi-bande libre L.

(b) Touts demi-bande T, n cn ider~otente avec IETI = 2 est iso-

morphe "_a L.

Preuve :

(a) Touts demi-bsnde de type deux est is~norphe ~ un quotient

de L (c'est ~ dire ~ L si les classes sont ~ un seul @l@ment).

120


Imaginons qu'une classe identifie deux roots distincts ~, 8 de Let

supposons flail : p <- n : llelt.

Tout mot m de longueur q sup@rieure ~ n contient @videnwent 8

conme facteur (i.e. ~ = U.e.~ avec U, 9~ L I , U et ~ n'@taut pas si-

multan@ment @gaux ~ I, la derni~re lettre (@ventuelle) de U distincte

de la premiere lettre de 8 et la derni~re de e distincte de la pre-

miere lettre @ventuelle de 9). a est donc @quivalent ~ m' = ~.~.~ de

longueur strictement plus petite que n darts le cas p < n. Sip = n,

et 8 ont m~me longueur, ne commencent donc nine terminent par la

re@me lettre et l'@valuation de a' = ~.~.~ amine doric un raccourcis-

sement d'une ou deux unit@s sur la longueur de ~. Par ce ph@non~ne

de r@duction de longueur, le quotient est alors fini.

(b) Une demi-bande v@rifiant les ~oth~ses de (b) me peut @tre

de torsion d'apr~s la proposition I ; elle est donc infinie de type

deux, donc isomorphe ~ L d'apr~s (a).

Nous nous int@resserons d@sormais aux demi-bandes finies de

type deux.

III-2 - STRU~ DES EEMI-BANDES FINIES DE TYPE DEUX

Nous ferons d'abord quelques rappels classiques. Six est un

@l@ment de torsion d'un demi-groupe M, on rappelle que l'indice de

x et !a p@riode de x sont respectivement !es deux entiers kx et n x

(kx > 0 n x > O) ayant la propri@t@ caract@ristique :

k+s x k <~>k> ~x x = et s - O (rood n x)

Darts ce cas, le plus petit exposant ~ (entier) tel que x a = e x

(l'ide~potent engendr@ par x) a la fonne a = kn x avec

knx -> kx > (k-1)nx"

Nous rappelons @galement [5] qu'une m@thode propos@e pour @tu-

dier la structure des idempotents E M d'un demi-groupe M consiste

utiliser les relations suivantes :

• Le pr@ordre d'abso~ption ~ droite sur E N d@fini par

def e ~ f < > fe : e (e absorbe f, ~ droite)

121


dont l'~quivalence associ@e est not@e - et appel@e isovalence droite.

• Le pr@ordre d'absorption ~ gauche sur E M d@fini par

def e < f < > ef = e (e absorbe f, ~ gauche).

Y

L'@quivalence associ@e @rant not@e = et appel@e isovalence ~ . Y

• L'intersection de ces deux pr@ordres est un ordre (appel@

ordre d'absorption) et not@

def e < f < > [ef = fe = e] (e absorbe f).

Par suite l'intersection des deux @quivalences - et - est l'@ga- Y

lit@ et donc une classe d'isovalence gauche coupe une classe d'isova-

lence droite en un @l@ment au plus.

IIen r@sulte que si !e quadruplet (e,f,g,h) d'ider~potents dis-

tincts ou non, v@rifient les isovalences selon la figure (nous dirons

encore : "fon~ent un rectangle") :

h Y g

e ........ f Y

alors g : f <=~> h : e et de m~me e : f <~=> h : g,

(rectangle aplati gauche ou droit).

~q~.n g = e <---> h = f <----> e = f = g = h,

(rectangle d@g~n@r~ en un point).

THEOFZ~E 4 : Soit Tune demi-bande finie engendr@e par les deux

idempotents distincts a et b.

(I) Test union des deux sous de~i-groupes triviaux {a} e_~t {b}

et des quatre sous demi-gro~s monog~nes engendr@s respectivement

par ab, ba, aba, bah. Ces ~ @l@ments ont re@me p@riode et les

~eux possibles de valeurs prises par leurs indices sont .respective-

ment

122


(k,k,k,k) (k+l,k+l,k,k)

{ (~+1,x,~,x) ~ (x+1,x+1,x+1,x)

(k,k+l,k,~) [(k+l,k+l,~,k+l)

(Les jeux [email protected] par une accolade correspondent ~ une situation

sym@tri~ue par @chan~e de a et b).

(2) L'ensemble % est la r@union de (a,b} e_~t du rectar~l e

% : (eaba, eba , ebab, eab) @ventuellement aplati ou r~duit ~ un

point. En outre

eab a < a et eba b < b.

~MA~UE : Le r@sultat (2) peut @tre

ral :

visualis@ par le sch@ma g@n@-

6 /

~6~ J

Ce sch@ma pouvant donner lieu ~ des d@g@n@rescences.

D~monstration :

(1) T @tant l'image par un morphisme, de la demi-bande libre L,

Test bien l'union de 6 demi-groupes monog~ne conform~ment aux pro-

pri@t@s de L (Ill-l).

Nous avons les deux s@ries de relations @videntes (~ n'utiliser

qu'avec des exposants strictement positifs) :

(ab) p = a(ba)P-~ = (aba)P-~ = a(bab) p-1

(aba) p : (ab)Pa = a(ba) p : a(bab)P-la

et deux autres s@ries analogues par @change de a et b.

Soient (nl,Xl) , (n2,k2) , (~,13) , (n4,k 4) les p@riodes et in-

dices respectifs de ab, ha, aba, bab.

123


nl+l I 11 De (ab) : (ab) on d@duit (par la deuxi~me s@rie de rela-

nl+l I l 1 tions) (aba) : (aba) d'o~ ~I ~ ~3 et n I ~ 0 (mod n3). On tire

de m@me (ba) nl+kl+l ~I+I : (b'a) d'o~ XI+I ~ ~2 et n I ~ 0 (modn2).

Enfin de lam@me mani~re kl ~ X4 nl ~ 0 (modn4).

~2 +n ~2 On proc~de ainsi ~ partir ~e (ba) = (ba) , puis de

X3 ~4 (aba) k3+n3 = (aba) et enfin de (bah) k4+n4 = (bab)

On arrive aux conclusions @nonc@es en (I).

(2) E T con~0orte d'apr@s (!) au plus 6 @l@ments a, b, Cab , eba,

eaba, eba b. Nous avons :

eab= (ab) sn eba = (ba) tn Cab a = (aba) un eba b = (bab) vn

Ii est @vident alors que l'on a :

eab ~ b, Cab ~ a, Cab a < a

et des relations analogues par @change de aet b.

On d@duit @galement

Cab eaba = (ab)Sn(aba) un = (aba) (u+s)n- = (aba) un = Cab a

et de re@me

Cab a Cab = Cab d'oG Cab a ~ Cab

On compl~te de n~me la d@monstration de (2).

III-3 - CLASSIFICATION DES DEMI-BANLES DE TYPE DEUX

Nous sonmes en mesure d'exhiber toutes les classes d'isomor-

phisme de demi-bandes de type deux. Nous avons utilis@ la technique

de la pr@sentation par g@n@rateurs et relations, guid@e par le

th@or~me 4 pr@c@dent. Nous n'allons pas expliciter tous les calculs

justificatifs qui n'exigent aucune prouesse sp@ciale sinon une cer-

taine patience.

On @tablit d'abord que dans le cas g@n@ral ~ 6 idempotents avec

une p@riode n et un param~tre I pour les indices, quatre situations

non isomorphes se pr@sentent :

124

C. BENZAKEN, H.C. ~AYR

>'ab %ab (ba) x

= : = = <~> I et

[ (ab) ~+n (ab) x

kab = k+l, ~a = kaba : ~ab : k <==> (ba) k+n = (ba) k

(bob) x+n = (bab) ~

kab : kba = ~+1, kab a = ~ab : k <==> et (aba) k+n (aba) ~

kab : ~ba = Xaba : k+ l , kba b : 1 < ~ > (bab~ +n = (bah) k

Ensuite deux types de d@g@n@rescencesr@duisant !e hombre d'idem-

potents sont @tudi@es

- a = eab a <~> a = (aba) n

le jeu d'indices @tant (I,1,I,1) et la p@riode n.

- La d@g@n@rescence lin@aire. Par exergole eba b : eba.

Elle inlolique n = I (demi-groupe combinatoire) et comporte quatre

cas non isomorphes :

indices

(~,~,k,~) ~ (aba) ~ : (ab) k et (Dab) ~ : (ba) k

(k+l,k,k,k) ~ (bab)k : (ba) k

(k+l,k+l,k,k) <~> (aba) k : (sb) k+l et (bob) ~ : (ba) k+l

(k+1,~+I,~+1,~) <~=> (bah) ~ = (ba) ~+1

Par combinaison de ces types de d@g@n@rescence on peut @tablir

les tables qui figurent ~ la fin et qui donnent toutes les classes

d'isomorphisme ; la situation des ide~potents, la pr@sentation stan-

dard et l'ordre de la demi-bande darts chaque classe, figurent dans

ces tables. On peut en d@duire ais@ment le nombre de demi-bandes de

type deux ayant un ordre donn@.

125

C. BENZAKEN, H.C. mAYR

kP~=.o ,re PRE5ENT'RTio~v5

~qrL

S L ~ t , MB

K ¢ ~ a r g u ¢ ~

i

~') =(=J'9 . . . . .

h,,~t,t,¢

)

, = 1 = ) % ~ ~ ,

1"

6=61x__16=)~ ~ ).,1 ),,1 X ~ 4X+~- l " & a,u~e

1 "

J

I

126

C. BENZAKEN, H.C. "AYR

\P,,I,J (,~ P RESEN T#,TioNs

~xe m a r ciu~a

6)~,: o.)X o,,,,.~+ ,,. "..;v¢ (o. (6 ), ,k ,k X 4X-4 ,; x=~

G (~,,,,.pot,~,,,~ i

;so,,o'9,6 , ,,,,, ,,,,

5

0 . : ~ 6 4 4 t 4

{

cb, ~i-£ o..,,&

J oy,?,~-

,,,,, ,,

~ = ,bc,.

)._

~ ' ~ " 9 ' ~"~

|

• I cc:6o.6 I 14 .'* I .Z o ---,J6

;so,,,, '9,~

127


REFERENCES

[I] Clifford A.H. and G.B. Preston, The Al~ebraic theory of semi- groups. A.M.S. 1 (1961), 0-224.

[2] De Bakker J.W., Axiom system for simple assignment statements. Symposium on Seman-'~s o--~Igorl--~hmic l'-'-~--=-~guages, Springer~-Verlag, Lect. Notes in Math. 188 (1971), 1-22.

[3] Eberhart C., W. Williams and L. Kinch, Id~otent,generated semi-groups. Journ. Of the Australian Math. Soc. 15

p~(Feb. 1973), 27-34.

[4] Krohn K., J.L. Rhodes and B.R. Tilson, The prime decomposition theorem of the ~ebraic theory of machine~---s~--~--chines," Languages ~--groups =(M. ArbibT~--~c~dq'-press. (i968), 81-125.

[5] Kuntzmann J., Sur les idempotents d'un monofde. Bull. Math. de la Soc. Math. d'6 I~ ~ep. de Ro~e, T ~ 2 , n ° 2 (1970), 181-188.

[6] Perrot J.F., Conmunication personmelle (Jui l . 1972).

C. BENZAKEN - Institut de Recherches en Math@matiques Avanc@es, Grenoble, Universit@ 1

H.C. MAYR - Institut de Recherches en Math@matiques Avanc@es, Grenoble, Universit@ I et Universit@ de Karlsruhe, D75, 41, Allemagne de l'Ouest.

R e c e i v e d June 18, 1974; i n r e v i s e d f o r m D e c e m b e r ZZ, 1974

128

Documents

Notion de demi-bande demi-bandes de type deux