Algorithmic aspects of finite semigroup theory, a tutorial

pages

English

Documents

Écrit par
Jean-Éric Pin

Publié par
Ornui

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

English

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Ornui

Langue

English

Part IGroup radicalGroup radicalThe group radical of a ﬁnite 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 deﬁned on M by u6 v iﬀ, for allP Px,y∈M,xvy∈P ⇒xuy∈P¯Denote by P the complement of P. Then u6 vPiﬀ 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 iﬀ there exist x,y∈MPsuch that¯xuy∈P and xvy∈PTherefore, u6 v iﬀ 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 ﬁrst search (starting from eachvertex labeled by (0,1)) and set to 0 the ﬁrstcomponent of the label of all visited vertices ...

Voir

Publié par

Ornui

Langue

English

Group radical

PartI

Group radical

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

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 preorder6Pis deﬁned onMbyu6Pviﬀ, for all x y∈M, xvy∈P⇒xuy∈P

¯ Denote byPtheocelpmtnemofP. Thenu66Pv iﬀ there existx y∈Msuch that

¯ xuy∈Pandxvy∈P

LIAFA,CNRSnadUnievsrityParisVII

FA,CLIAisytvirednnURNaStaynesThIIsVriPaionomderedrocitcodafibBn21

∗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 thatu66Pviﬀ there existx y∈M such that ¯ xuy∈Pandxvy∈P

Therefore,u66Pviﬀ 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]

[u66Pv] [v66Pu]

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

LIAFA, CNRS and University Paris VII

Constraint propagation

(3)

(4)

Do adepth ﬁrst 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∼Pv 0(1(1)0)fifiuv66PPvu (00)ifuandvare incomparable

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

Voir