Algorithmic aspects of finite semigroup theory, a tutorial

Jean-Éric Pin

Description

Part IGroup radicalGroup radicalThe group radical of a finite monoid M is thesmallest submonoid D(M) of M containing theidempotents and closed under weak conjugation: ifsts =s and d∈D(M), then sdt,tds∈D(M).LIAFA, CNRS and University Paris VIIComputation of the radicalInitialisation : D(M) =E(M)For each d in D(S)For each weakly conjugate pair (s,t)add sdt and tds to D(S)add D(S)d to D(S).3Time complexity in 0(|S| ).LIAFA, CNRS and University Paris VII6Part IISyntactic ordered monoidIf P is a subset of a monoid M, the syntacticpreorder6 is defined on M by u6 v iff, for allP Px,y∈M,xvy∈P ⇒xuy∈P¯Denote by P the complement of P. Then u6 vPiff there exist x,y∈M such that¯xuy∈P and xvy∈PLIAFA, CNRS and University Paris VII1The syntactic ordered monoid of ab in B2∗ ∗1 0∗ aab∗ ∗ab a b ba∗b ba∗ ∗0 1LIAFA, CNRS and University Paris VII66An algorithm for the syntactic preorderLet G be the graph with M×M as set of verticesand edges of the form (ua,va)→ (u,v) or(au,av)→ (u,v).We have seen that u6 v iff there exist x,y∈MPsuch that¯xuy∈P and xvy∈PTherefore, u6 v iff the vertex (u,v) is reachableP¯in G from some vertex of P ×P.LIAFA, CNRS and University Paris VII66The algorithm (2)(1) Label each vertex (u,v) as follows:(0,1) if u∈/ P and v∈P [u6 v]P(1,0) if u∈P and v∈/ P [v6 u]P(1,1) otherwise(2) Do a depth first search (starting from eachvertex labeled by (0,1)) and set to 0 the firstcomponent of the label of all visited vertices ...

Informations

• Publié par: Ornui
• Nombre de lectures: 18
• Langue: English

Extrait

Group radical

PartI

Group radical

Thegroup radicalof a finite monoidMis the smallest submonoidD(M)ofMcontaining the idempotents and closed under weak conjugation: sts=sandd∈D(M), thensdt tds∈D(M).

if

LIAFA, CNRS and University Paris VII

Computation of the radical

Initialisation:D(M) =E(M)

ForeachdinD(S)

Foreachweakly conjugate pair addsdtandtdstoD(S) addD(S)dtoD(S).

Time complexity in0(|S| 3 ).

(s t)

LIAFA, CNRS and University Paris VII

PartII

Syntactic ordered monoid

IfPis a subset of a monoidM, thesyntactic preorder6 P is defined onMbyu6 P viff, for all x y∈M, xvy∈P⇒xuy∈P

¯ Denote byPtheocelpmtnemofP. Thenu66 P v iff there existx y∈Msuch that

¯ xuy∈Pandxvy∈P

LIAFA,CNRSnadUnievsrityParisVII

FA,CLIAisytvirednnURNaS taynesTh IIsVriPa ionomderedrocitcodafibBn 2 1

∗ ab a b ∗ ba

a b

∗ ab

∗ 0

∗ 1

∗ 0

∗ 1

∗ ba

An algorithm for the syntactic preorder

LetGbe the graph withM×Mas set ofvertices andedgesof the form(ua va)→(u v)or (au av)→(u v).

We have seen thatu66 P viff there existx y∈M such that ¯ xuy∈Pandxvy∈P

Therefore,u66 P viff the vertex(u v)is reachable ¯ inGfrom some vertex ofP×P.

LIAFA, CNRS and University Paris VII

The algorithm (2)

(1)

(2)

(u v)as follows:

Label each vertex    (01)ifu∈ Pandv∈P (10)ifu∈Pandv∈ P   (11)otherwise

[u66v]

[u66 P v] [v66 P u]

Do a depth first search (starting from each vertex labeled by(01)) and set to0the first component of the label of all visited vertices.

LIAFA, CNRS and University Paris VII

Constraint propagation

(3)

(4)

Do adepth first search(starting from each vertex labeled by(00)or(10)) and set to thesecondcomponent of the label of all visited vertices. The label of each vertex now encodes the syntactic preorderofPas follows:  (11)ifu∼ P v   0( 1(   1 )0 ) fi fi u v 6 6 P P v u   (00)ifuandvare incomparable

0

LIAFA, CNRS and University Paris VII

Computation of the syntactic preorder

LetM={1 a b}withaa=ba=aand ab=bb=b. LetP={a}.

a1

a b

1 b

a a

11

b b

b1

b a

ILFA,ANCRS

1 a

nadUnievrsiytaPirsVII

Computation of the syntactic preorder

LetM={1 a b}withaa=ba=aand ab=bb=b. LetP={a}.

Initial labels

(10) a1

(10) a b

(11) 1 b

(11) a a

(11) 11

(11) b b

(11) b1

(01) b a

ILFA,ACNRS

(01) 1 a

andnUiversiytParisIVI

Computation of the syntactic preorder

LetM={1 a b}withaa=ba=aand ab=bb=b. LetP={a}.

DFS from(b a)

(10) a1

(10) a b

(11) 1 b

(11) a a

(11) 11

(11) b b

(11) b1

(01) b a

ILFA,ANCRS

(01) 1 a

nadnUiversiytParisVII

Computation of the syntactic preorder

LetM={1 a b}withaa=ba=aand ab=bb=b. LetP={a}.

DFS from(b a)

(10) a1

(10) a b

(11) 1 b

(11) a a

(11) 11

(11) b b

(11) b1

(01) b a

ILAFA,CNRS

(01) 1 a

andUnivesrityaPirsIVI