Profinite semigroups and applications in
Computer Science
Jorge Almeida
Departamento Matem´atica, CMUP
Faculdade de Ciˆencias, Universidade do Porto
Porto, Portugal
http://www.fc.up.pt/cmup/jalmeida/
October, 2011
´Ustav matematiky a statistiky
Pˇr´ırodovˇedeck´a fakulta
Masarykova univerzita
1 / 113
Abstract
Finite semigroups appear naturally in Computer Science, namely as syntactic semigroups of regular
languages, transition semigroups of finite automata, or as finite recognizing devices on their own.
Eilenberg’s correspondence theorem gives a general framework for the classification of regular
languages through algebraic properties of their syntactic semigroups. Here is the resulting typical
problem on the algebraic side: a recursively enumerable set R of finite semigroups is given and one
wishes to decide whether a given finite semigroup is a homomorphic image of a subsemigroup of a
finite product of members of R. Since such a problem is often undecidable, special techniques have
been devised to handle special cases. Relatively free profinite semigroups turn out to be quite
useful in this context. They play the role of free algebras in Universal Algebra, capturing in their
algebraic-topological/metric structure combinatorial properties of the corresponding classes of
languages.
The aim of this short course is to introduce reltively free profinite semigroups and to explore two
topics in which there have been significant recent developments, namely the separation of a given
word from a given regular language by a regular language of a special type (for instance, a group
language), and connections with symbolic dynamics.
Tentative syllabus and preliminary references:
1. Relatively free profinite semigroups. (1 lecture)
Reference:
[1] J. Almeida, Profinite semigroups and applications, in ”Structural Theory of Automata, Semigroups, and
Universal Algebra”, V. B. Kudryavtsev and I. G. Rosenberg (eds.), Proceedings of the NATO Advanced Study
Institute on Structural Theory of Automata, Semigroups and Universal Algebra (Montr´eal, Qu´ebec, Canada,
7-18 July 2003), Springer, New York, 2005, pp. 1-45.
2. 2. Separating words and regular languages. (2 lectures)
Reference:
[2] S. Margolis, M. Sapir, and P. Weil, Closed subgroups in pro-V topologies and the extension problem for
inverse automata, Int. J. Algebra and Comput. 11 (2001) 405-455.
3. Relatifely free profinite semigroups and Symbolic Dynamics. (2 lectures)
Reference:
[1] (see above).
2 / 113
Part I
Relatively free profinite semigroups
3 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
4 / 113
A regular language is a subset of the free monoid A∗ on an
alphabet A admitting a regular expression, i.e., a formal
expression describing it in terms of the empty set ∅ and the
letters a ∈ A using the following operations:
(K, L) → K ∪ L (union)
(K, L) → KL (concatenation)
L → L∗
(Kleene star)
The syntactic congruence of the language L ⊆ A∗ is the binary
relation σL on A∗ defined by:
u σL v if ∀ x, y ∈ A∗
(xuy ∈ L ⇔ xvy ∈ L).
The syntactic monoid M(L) of the language L ⊆ A∗ is the
quotient monoid A∗/σL.
5 / 113
Theorem 1.1
The following conditions are equivalent for a language L over a
finite alphabet A:
(1) L is regular;
(2) L is recognized by some finite automaton;
(3) L is recognized by some finite complete deterministic
automaton;
(4) the syntactic monoid A∗/σL on A∗ is finite;
(5) L is recognized by some homomorphism ϕ : A∗ → M into a
finite monoid, in the sense that L = ϕ−1ϕL.
Corollary 1.2
The set Reg(A∗) of all regular languages over the alphabet A is a
Boolean subalgebra of the Boolean algebra of all subsets of A∗.
6 / 113
Example: (restricted) Dyck languages
Regular expression: L1 = (ab)∗
Minimal (incomplete) automaton: 0 1
a
bTransition monoid (M(L1)):
0 1
a 1 b
- 0
ab 0 ba
- 1
0 - a
b ab ba 0
a 0 ab 0 a 0
b ba 0 b 0 0
ab a 0 ab 0 0
ba 0 b 0 ba 0
0 0 0 0 0 0
Presentation: a, b; aba = a, bab = b, a2
= b2
= 0 .
One may then compute Green’s relations, which are summarized
in the following eggbox picture:
• same row: elements generate the same right ideal (R)
• same column: elements generate the same left ideal (L)
• elements above are factors of elements below (≥J )
• ∗
e marks an idempotent (e2
= e)
• the“eggboxes”are the J -classes (J = ≥J ∩ ≤J )
• D = R ◦ L = L ◦ R
• in a finite monoid, D = J
*0
a *ab
*ba b
*1
7 / 113
Regular expression: L2 = (a(ab)∗
b)∗
Minimal (incomplete) automaton: 0 1 2
a
b
a
b
Presentation of syntactic monoid M(L2):
a, b; aba = a, bab = b, a2
b2
a2
= a2
, b2
a2
b2
= b2
,
ab2
a = ba2
b, a3
= b3
= 0
Eggbox picture:
*0
aa aab *aabb
baa *abba abb
*bbaa bba bb
a *ab
*ba b
*1
8 / 113
Dyck language: L∞ = n≥0 Ln, where L0 = {1},
Ln+1 = (aLnb)∗.
Recognition by infinite automaton:
0 1 2 · · · n n + 1 · · ·
a
b
a
b
a
b
a
b
a
b
a
b
Syntactic monoid: M(L∞) = a, b; ab = 1 .
Eggbox picture:
∗
1 a a2
· · · an
an+1
· · ·
b ∗
ba ba2
· · · ban
ban+1
· · ·
b2
b2
a ∗
b2
a2
· · · b2
an
b2
an+1
· · ·
...
...
...
...
...
...
bn
bn
a bn
a2
· · · ∗
bn
an
bn
an+1
· · ·
bn+1
bn+1
a bn+1
a2
· · · bn+1
an ∗
bn+1
an+1
· · ·
...
...
...
...
...
...
9 / 113
Exercise 1.3
Consider the transition semigroup S of the following infinite automaton:
2 4
c
ÐÐ
6
c
ÐÐ
8
c
ÐÐ
· · ·
c
~~
1
a
yy
b GG 3
a
yy
b GG 5
a
yy
b GG 7
a
yy
b GG · · ·
1. Note that, in S, aca is a factor of a but a is not regular.
2. Verify that S admits the following presentation:
a, b, c; baca = a, bacb = b2
ac = b, cbac = c,
a2
= ab = bc = c2
= 0 .
3. Show that S has two J -classes, one of which is reduced to zero.
4. Show that the non-trivial J -class of S consists of two infinite
D-classes, one of which is regular and a bicyclic monoid, while the
other is not regular and has only one L-class. All H-classes of S are
trivial.
10 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
11 / 113
A variety of languages is a correspondence V associating with
each finitely generated free monoid A∗ a set V(A∗) of
languages over the finite alphabet A such that the following
conditions hold:
1. V(A∗
) is a Boolean subalgebra of Reg(A∗
);
2. if L ∈ V(A∗
) and a ∈ A, then the following languages also
belong to V(A∗
):
a−1
L = {w ∈ A∗
: aw ∈ L}
La−1
= {w ∈ A∗
: wa ∈ L};
3. if ϕ : A∗
→ B∗
is a homomorphism and L ∈ V(B∗
), then
ϕ−1
(L) ∈ V(A∗
).
A pseudovariety of monoids is a nonempty class V of finite
monoids which is closed under taking homomorphic images,
submonoids, and finite direct products.
12 / 113
Theorem 2.1 (Eilenberg [Eil76])
The complete lattices of varieties of languages and of
pseudovarieties of monoids are isomorphic. More precisely, the
following correspondences are mutually inverse isomorphisms
between the two lattices:
to a variety V of languages, associate the pseudovariety V
generated by all syntactic monoids M(L) with L ∈ V(A∗) for
some finite alphabet A;
to a pseudovariety V, associate the variety of languages V
such that, for each finite alphabet A, V(A∗) consists of the
languages L ⊆ A∗ such that M(L) ∈ V.
13 / 113
Thus, problems about varieties of languages admit a
translation into problems about pseudovarieties of monoids.
For instance, to determine if a language L ⊆ A∗ belongs to
smallest variety of languages containing two given varieties of
languages V and W is equivalent to determine if M(L)
belongs to the pseudovariety join V ∨ W.
Typically, we are given a recursively enumerable set R of finite
monoids and we want to determine an algorithm to decide
whether a given finite monoid M belongs to the pseudovariety
V(R) generated by R.
14 / 113
Mutatis mutandis, we have
languages L ⊆ A+ without the empty word 1;
syntactic congruence σL of L over A+:
u σL v if ∀ x, y ∈ A∗
(xuy ∈ L ⇔ xvy ∈ L).
syntactic semigroup A+/σL;
varieties of languages without the empty word;
pseudovarieties of semigroups;
Eilenberg’s correspondence in this setting.
15 / 113
Examples of pseudovarieties:
S: all finite semigroups
I: all singleton (trivial)
semigroups
G: all finite groups
Gp: all finite p-groups
A: all finite aperiodic
semigroups
Com: all finite
commutative
semigroups
J: all finite J -trivial
semigroups
R: all finite R-trivial
semigroups
L: all finite L-trivial
semigroups
Sl: all finite semilattices
RZ: all finite right-zero
semigroups
B: all finite bands
N: all finite nilpotent
semigroups
K: all finite semigroups in
which idempotents are left
zeros
D: all finite semigroups in
which idempotents are right
zeros
16 / 113
Important examples of instances of
Eilenberg’s correspondence
A language L ⊆ A+ is said to be star free if it admits an
expression in terms of the languages {a} (a ∈ A) using only
the operations: ∪ , A+ \ , and concatenation.
Theorem 2.2 ([Sch65])
A language over a finite alphabet is star free if and only if its
syntactic semigroup is finite and aperiodic.
17 / 113
A language L ⊆ A∗ is piecewise testable if it is a Boolean
combination of languages of the form A∗a1A∗a2A∗ · · · anA∗,
with the ai ∈ A.
Theorem 2.3 ([Sim75])
A language over a finite alphabet is piecewise testable if and only if
its syntactic semigroup is finite and J -trivial.
A language L ⊆ A∗ is locally testable if it is a Boolean
combination of languages of the forms A∗u, A∗vA∗, and wA∗,
where u, v, w ∈ A+.
Theorem 2.4 ([BS73, MP71])
A language L over a finite alphabet is locally testable if and only if
its syntactic semigroup S is finite and a local semilattice (i.e.,
eSe is a semilattice for every idempotent e ∈ S).
18 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
19 / 113
Definition 3.1
We say that a pseudovariety V is decidable if there is an algorithm
which, given a finite semigroup S as input, produces as output, in
finite time, YES or NO according to whether or not S ∈ V.
The semigroup S may be given in various ways:
extensively, meaning the complete list of its elements together
with its multiplication table;
as the transformation semigroup on a finite set Q
generated by a finite set A of transformations of Q ;
→ transition semigroup of a finite automaton (Q, A, δ, I, F);
by means of a presentation.
Different ways of describing S may lead to different
complexity results, when such an algorithm exists.
20 / 113
Of course, not all pseudovarieties are decidable.
For instance, if P is a non-recursive set of primes, then the
pseudovariety AbP, generated by all groups Z/pZ with p ∈ P,
contains a group Z/qZ of prime order q if and only if q ∈ P.
Since there are non-recursive sets of primes P, there are
pseudovarieties of the form AbP which are not decidable.
Question 3.2 (Very imprecise!!)
Are all“natural”pseudovarieties decidable?
21 / 113
There are many ways to construct new pseudovarieties from known
ones, that is by applying operators to pseudovarieties.
We proceed to introduce some natural operators.
Definition 3.3
Given a pseudovariety V, consider the classes of all finite
semigroups S such that, respectively:
LV: eSe ∈ V for every idempotent e ∈ S;
EV: E(S) ∈ V, where E(S) is the subsemigroup
generated by the set E(S) of all idempotents of S;
DV: the regular J -classes of S (are subsemigroups which)
belong to V;
V: the subgroups of S belong to V;
22 / 113
Let S be a finite semigroup and let D be one of its regular
D-classes.
Let ∼ be the equivalence relation on the set of group
elements of D generated by the identification of elements
which are either R or L-equivalent.
A block of D is the Rees quotient of the subsemigroup of S
generated by a ∼-class modulo the ideal consisting of the
elements which do not lie in D.
*
*
*
*
* *
*
*
*
*
*
*
* *
*
*
1 2 3 4 5 6
*
* * *
*
*
* *
1 3 6 2 4 5
The blocks of S are the blocks of its regular D-classes.
Definition 3.4
For a pseudovariety V, let BV be the class of all finite semigroups
whose blocks lie in V.
23 / 113
Proposition 3.5
For a pseudovariety V, the classes BV, DV, EV, LV, V are
pseudovarieties.
Moreover, if V is decidable then so are those pseudovarieties.
Proof.
We consider only the case of LV, leaving all other cases as exercises.
If ϕ : S → T is an onto homomorphism, with S ∈ S, and f ∈ E(T), then
∃e ∈ ϕ−1
(f ) ∩ E(S) and ϕ|eSe : eSe → fTf is an onto homomorphism
∴ LV is closed under taking homomorphic images.
If S ≤ T and e ∈ E(S), then eSe ≤ eTe
∴ LV is closed under taking subsemigroups.
If S, T are semigroups, e ∈ E(S), and f ∈ E(T), then
(e, f )(S × T)(e, f ) eSe × fTf
∴ LV is closed under taking finite direct products.
Given a finite semigroup, one can compute its set of idempotents E(S) and, for
each e ∈ E(S), the monoid eSe.
Provided V is decidable, one can then effectively check whether eSe ∈ V.
Hence one can effectively check whether S ∈ LV.
24 / 113
But, the most interesting operators are defined not in structural
terms but rather by describing generators: the resulting
pseudovariety is given as the smallest pseudovariety containing
certain semigroups which are constructed from those in the
argument pseudovarieties.
Definition 3.6
We say that a semigroup S divides a semigroup T, or that S is a
divisor of T, and we write S T, if S is a homomorphic image of
a subsemigroup of T.
Proposition 3.7
Let C be a class of finite semigroups. Then the smallest
pseudovariety V(C) containing C consists of all divisors of products
of the form S1 × · · · × Sn with S1, . . . , Sn ∈ C.
In particular, if C is closed under finite direct product, then V(C)
consists of all divisors of elements of C.
25 / 113
Let S and T be semigroups and let ϕ : T1 → End S be a
homomorphism of monoids, with endomorphisms acting on the left.
For s ∈ S and t ∈ T1, let ts = ϕ(t)(s).
The semidirect product S ∗ϕ T is the set S × T under the
multiplication
(s1, t1) · (s2, t2) = (s1
t1
s2, t1t2).
Definition 3.8
The semidirect product V ∗ W of the pseudovarieties V and W is
the smallest pseudovariety containing all semidirect products S ∗ T
with S ∈ V and T ∈ W.
Proposition 3.9
The pseudovariety V ∗ W consists of all divisors of semidirect
products of the form S ∗ T with S ∈ V and T ∈ W.
Proposition 3.10
The semidirect product of pseudovarieties is associative.
26 / 113
Definition 3.11
The Mal’cev product V m W of two pseudovarieties V and W is
the smallest pseudovariety containing all finite semigroups S for
which there exists a homomorphism ϕ : S → T such that T ∈ W
and ϕ−1(e) ∈ V for all e ∈ E(T).
Given two semigroups S and T, a relational morphism S → T is a
relation µ : S → T with domain S such that µ is a subsemigroup
of S × T.
Proposition 3.12
The pseudovariety V m W consists of all finite semigroups S such
that there is a relational morphism µ : S → T such that T ∈ W
and µ−1(e) ∈ V for all e ∈ E(T).
27 / 113
For a semigroup S, denote by P(S) the semigroup of subsets of S
under the product operation
X · Y = {xy : x ∈ X, y ∈ Y }.
Note that the empty set ∅ is a zero and P (S) = P(S) \ {∅} is a
subsemigroup.
Definition 3.13
For a pseudovariety V, denote by
PV: the pseudovariety generated by all semigroups of the
form P(S), with S ∈ V;
P V: the pseudovariety generated by all semigroups of the
form P (S), with S ∈ V.
Proposition 3.14
The pseudovariety PV consists of all divisors of semigroups of the
form P(S) with S ∈ V.
Similar statement for P .
28 / 113
Some examples of results on finite semigroups formulated in terms
of these operators:
1. J = N m Sl
2. DA = LI m Sl, DS = LG m Sl
3. R = Sl ∗ J [Sti73]
4. G ∨ Com = ZE (the pseudovariety of all finite semigroups in
which idempotents are central) [Alm95]
5. ESl = Sl ∗ G = Sl m G = Inv (the pseudovariety generated by
all finite inverse semigroups) [MP87, Ash87, Pin95],
ER = R ∗ G [Eil76], EDS = DS ∗ G [AE03]
6. PG = J ∗ G = J m G = EJ = BG
[MP84, HR91, Ash91, HMPR91, Pin95],
PJ = PV(Y ) [PS85, Alm95] where Y = Synt(a∗bc∗)
7. S = n≥0(A ∗ G)n ∗ A [KR65]
29 / 113
S =
n≥0
(A ∗ G)n
∗ A
The (Krohn-Rhodes) hierarchy (A ∗ G)n ∗ A
n≥0
is strict.
The smallest n such that a given finite semigroup S belongs to
(A ∗ G)n ∗ A is called the complexity of S, denoted c(S).
Let Tn denote the full transformation semigroup of an n-element
set It is known that c(Tn) = n − 1 [Eil76] and so certainly
c(S) ≤ |S| (since S → TS1 ).
Note 3.15
To know an algorithm to compute the complexity function is
equivalent to know algorithms to decide the membership problem
for each pseudovariety in the Krohn-Rhodes hierarchy.
30 / 113
This brings us to the following basic question:
Question 3.16
For the operators which were defined above in terms of generators,
do they preserve decidability?
Theorem 3.17 (Albert, Baldinger & Rhodes’1992
[ABR92])
There exists a finite set Σ of identities such that Com ∨ [[Σ]] is
undecidable.
Let C2,1 = a; a2 = 0 1.
Theorem 3.18 (Auinger & Steinberg’2003 [AS03])
There exists a decidable pseudovariety of groups U such that the
following pseudovarieties are all undecidable:
Sl ∗ U (= Sl m U), V(C2,1) ∨ U, PU (= P U).
31 / 113
The pseudovariety U is defined to be
U =
p∈A
Gp ∗ (Gf (p) ∩ Com) ∨
p∈D
(Gp ∩ Com)
where:
A and B constitute a computable partition of the set of
primes into two infinite sets;
f : A → B is an injective recursive function whose range
C = f (A) is recursively enumerable but not recursive;
D = B \ C is not recursively enumerable.
Exercise 3.19
Show that U is decidable.
32 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
33 / 113
Let V be a pseudovariety of semigroups.
For two words u, v ∈ A+, and T ∈ V, let
T |= u = v if, for every homomorphism ϕ : A+ → T, ϕ(u) = ϕ(v),
rV(u, v) = min{|S| : S ∈ V and S |= u = v},
dV(u, v) = 2−rV(u,v)
where we take min ∅ = ∞ and 2−∞ = 0.
Note 4.1
The following hold for u, v, w, t ∈ A+ and a positive integer n:
(1) rV(u, v) ≥ n if and only if, for every S ∈ V with |S| < n,
S |= u = v;
(2) dV(u, v) ≤ 2−n
if and only if, for every S ∈ V with |S| < n,
S |= u = v;
(3) dV(u, v) = 0 if and only if, for every S ∈ V, S |= u = v;
(4) min{rV(u, v), rV(v, w)} ≤ rV(u, w);
(5) min{rV(u, v), rV(w, z)} ≤ rV(uw, vz).
34 / 113
Definition 4.2
A function d : X × X → R≥0 is said to be a pseudo-ultrametric on
the set X if the following properties hold for all u, v, w ∈ X:
1. d(u, u) = 0;
2. d(u, v) = d(v, u);
3. d(u, w) ≤ max{d(u, v), d(v, w)}.
We then also say that X is a pseudo-ultrametric space.
If instead of Condition 3, the following weaker condition holds
4. d(u, w) ≤ d(u, v) + d(v, w) (triangle inequality).
then d is said to be a pseudo-metric on X, and X is said to be a
pseudo-metric space. If the following condition holds
5. d(u, v) = 0 if and only if u = v,
then we drop the prefix“pseudo”.
35 / 113
A function f : X → Y between two pseudo-metric spaces is said to
be uniformly continuous if the following condition holds:
∀ > 0 ∃ δ > 0 ∀ x1, x2 ∈ X d(x1, x2) < δ ⇒ d(f (u), f (v)) < .
Proposition 4.3
1. The function dV is a pseudo-ultrametric on A+
.
2. The multiplication is contractive:
dV(u1u2, v1v2) ≤ max{dV(u1, v1), dV(u2, v2)}.
In particular, the multiplication on A+
is uniformly continuous.
For a (pseudo-ultra)metric d, u ∈ X, and a positive real number ,
consider the open ball
B (u) = {v ∈ X : d(u, v) < }.
The point u is the center and is the radius of the ball.
A metric space that can be covered by a finite number of balls of
any given positive radius is said to be totally bounded.
36 / 113
Proposition 4.4
The metric space (A+, dV) is totally bounded.
Proof.
Let n be a positive integer such that 2−n
< . Note that, up to
isomorphism, there are only finitely many semigroups of cardinality at
most n in V. For such a semigroup Si consider all possible
homomorphisms ϕi,j : A+
→ Si , let S = i,j Si and
ϕ : A+
→ S
u → (ϕi,j (u))i,j .
Then S ∈ V and dV(u, v) < 2−n
if and only if ϕ(u) = ϕ(v).
For each s ∈ S, choose us ∈ A+
such that ϕ(us) = s.
For v ∈ A+
and s = ϕ(v), we have ϕ(v) = ϕ(us), and so v ∈ B (us).
We have thus shown that A+
= s∈S B (us).
37 / 113
A sequence (un)n in a (pseudo-ultra)metric space X is said to
be a Cauchy sequence if
∀ > 0 ∃ N m, n ≥ N ⇒ d(um, un) < .
Note that every convergent sequence is a Cauchy sequence.
The space X is complete if every Cauchy sequence in X
converges in X.
38 / 113
Theorem 4.5
Let X be a pseudo-(ultra)metric space. Then there exists a complete
metric space ˆX and a uniformly continuous function ι : X → ˆX with the
following universal property: for every uniformly continuous function
f : X → Y into a complete metric space Y , there exists a unique
uniformly continuous function ˆf : ˆX → Y such that ˆf ◦ ι = f .
X
ι GG
f
22
ˆX
ˆf

Y .
X
ι

γ
11
ˆX
ˆγ
CC Z.
ˆι
kk
In particular, if γ : X → Z is another uniformly continuous function into
another complete metric space with the above universal property then the
induced unique uniformly continuous mappings ˆι : ˆX → Z and ˆγ : Z → ˆX
are mutually inverse.
The“unique”space ˆX of Theorem 4.5 is called the Hausdorff
completion of X.
39 / 113
It may be constructed in the same way that the real numbers are
obtained by completion of the rational numbers. Here is a sketch:
(a) consider the set C ⊆ XN
of all Cauchy sequences of elements
of X;
(b) note that, for s = (un)n and t(vn)n in C, the sequence of real
numbers d(un, vn) n
is a Cauchy sequence and, therefore, it
converges; its limit is denoted d(s, t);
|d(un, vn) − d(um, vm)|
≤ |d(un, vn) − d(un, vm)| + |d(un, vm) − d(um, vm)|
≤ d(un, um) + d(vn, vm)
(c) Step (B) defines a pseudo-(ultra)metric on C;
(d) for s = (un)n and t(vn)n in C, let s ∼ t if d(s, t) = 0; this is
an equivalence relation on C; the class of s is denoted s/∼;
(e) let ˆX = C/∼ and put d(s/∼, t/∼) = d(s, t), which can be
easily checked to be defined;
(f) finally, let ι : X → ˆX map each u ∈ X to the ∼-class of the
constant sequence (u)n, and check that this mapping is
uniformly continuous and has the appropriate universal
property.
40 / 113
Note that ι(X) is dense in ˆX.
In particular, we may consider the Hausdorff completion of the
pseudo-ultrametric space (A+, dV), which is denoted ΩAV.
Since the multiplication of A+ is uniformly continuous with
respect to dV, it induces a uniformly continuous multiplication
in ΩAV:
A+ × A+ µ
(mult.)
GG
ι×ι

A+
ι

ΩAV × ΩAV
ˆµ
GG ΩAV
41 / 113
We endow each finite semigroup S with the discrete metric:
d(s, t) =
0 if s = t
1 otherwise
Since ι(A+) is dense in ΩAV, multiplication in ΩAV is
associative, and thus ΩAV is naturally a semigroup.
From hereon, we write d for dV. The context should leave
clear which pseudovariety is involved.
42 / 113
Note that, for S ∈ V, every homomorphism ϕ : A+ → S is
uniformly continuous with respect to d.
d(u, v) < 2−|S|
⇒ d(ϕ(u), ϕ(v)) = 0.
Thus, ϕ induces a unique uniformly continuous mapping
ˆϕ : ΩAV → S such that the following diagram commutes:
A+ ι GG
ϕ
44
ΩAV
ˆϕ

S.
One can easily check that ˆϕ is a homomorphism:
ˆϕ(uv) = lim ϕ(ι(unvn)) = lim ϕ(ι(un))ϕ(ι(vn))
= lim ϕ(ι(un)) · lim ϕ(ι(vn)) = ˆϕ(u) ˆϕ(v).
43 / 113
Given u, v ∈ ΩAV and S ∈ V, we write S |= u = v if, for every
homomorphism ϕ : A+
→ S (which is determined by ϕ|A), the
equality ˆϕ(u) = ˆϕ(v) holds.
We call the formal equality u = v a V-pseudoidentity.
Note that, if u = lim un, v = lim vn, and S ∈ V, then S |= u = v if
and only if S |= un = vn for all sufficiently large n.
Given distinct elements u, v ∈ ΩAV, there exists a positive integer
m such that d(u, v) ≥ 2−m
.
Consider sequences of words (un)n and (vn)n such that u = lim ι(un)
and v = lim ι(vn).
Then, for sufficiently large n, d(u, ι(un)) < 2−m
and
d(v, ι(vn)) < 2−m
.
Hence d(un, vn) = d(ι(un), ι(vn)) ≥ 2−m
for all sufficiently large n.
It follows that every S ∈ V with |S| < m fails the identity un = vn
and, therefore, also the pseudoidentity u = v.
44 / 113
Proposition 4.6
For u, v ∈ ΩAV, we have d(u, v) = 2−r(u,v), where
r(u, v) = min{|S| : S ∈ V and S |= u = v}.
Proof.
We have already shown that d(u, v) ≥ 2−m implies r(u, v) ≤ m.
The converse, as well as how the equivalence gives the proposition
are left as an exercise.
45 / 113
Recall that a metric space is compact if every sequence admits
some convergent subsequence. Equivalently, every covering by
open subsets contains a finite covering.
Proposition 4.7
1. If X is a totally bounded pseudo-metric space, then ˆX is also
totally bounded.
2. If X is a totally bounded complete metric space, then X is
compact.
46 / 113
Proof.
1. Given > 0, let u1, . . . , um ∈ X be such that X =
m
i=1 B /2(ui ).
Then ˆX =
m
i=1 B (ι(ui )) since every element of ˆX is at distance at most
/2 of some element of ι(X).
2. For each positive integer m, let Fm be a finite subset of X such that
X = x∈Fm
B2−m (x) and consider an arbitrary sequence (un)n in X.
For infinitely many indices n, the un belong to the same B2−1 (x1). Let k1
be the first of these indices. Similarly, among the remaining such indices,
there are infinitely many n such that the un belong to the same B2−2 (x2).
We let k2 be the first of them. And so on.
We thus construct a subsequence (ukn
)n with the property that
d(ukm
, ukn
) ≤ 2− min{m,n}+1
,
if p = min{m, n}, then ukm , ukn ∈ B2−p (xp), which yields
d(ukm , ukn ) ≤ d(ukm , xp) + d(xp, ukn ) ≤ 2−p
+ 2−p
whence a Cauchy sequence and, therefore, convergent.
47 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
48 / 113
By a pro-V semigroup we mean a semigroup S endowed with
a metric such that the following properties hold:
1. S is compact;
2. the multiplication is uniformly continuous (metric semigroup);
3. for every pair u, v of distinct elements of S, there is a uniform
continuous homomorphism ϕ : S → T into a semigroup
from V such that ϕ(u) = ϕ(v) (S residually in V).
By a profinite semigroup we mean a pro-S semigroup.
49 / 113
Proposition 5.1
Let S be a pro-V semigroup. Then there is a sequence (Sn)n∈N of
semigroups from V and an injective homomorphism
ϕ : S → n∈N Sn such that, for each component projection
πm : n∈N Sn → Sm, the homomorphism πm ◦ ϕ is uniformly
continuous.
We may define in n∈N Sn a metric structure by letting
d(u, v) =
n∈N
2−n
dn(πn(u), πn(v))
where dn is the discrete metric on Sn. Then ϕ is uniformly
continuous. In particular, the image T of ϕ is closed in n∈N Sn,
being a compact subset.
50 / 113
Note that the sequence (Sn)n∈N may be chosen so that there
is a finite bound on the number of generators of the Sn if and
only if S is finitely generated in the sense that there is a finite
subset which generates a dense subsemigroup.
On the other hand, if there is no such bound, one can show
that S cannot have a countable dense subset, while it is easy
to see that a compact metric space always admits a countable
dense subset.
Proposition 5.2
Every pro-V metric semigroup is finitely generated.
51 / 113
For a finite set A, we say that the pro-V semigroup S is freely
generated by A if there is a mapping γ : A → S such that
γ(A) generates a dense subsemigroup of S and the following
universal property is satisfied, where ϕ : A → T is an aribtrary
mapping into a pro-V semigroup T, and ˆϕ is a unique
continuous homomorphism:
A
γ
GG
ϕ
11
S
ˆϕ

T
Theorem 5.3
For a pseudovariety of semigroups V and a finite set A, the metric
semigroup ΩAV is a pro-V semigroup freely generated by A via the
mapping ι|A.
52 / 113
Proof.
Let S be a pro-V semigroup and let (Sn)n∈N be a countable family of
semigroups from V as given by Proposition 5.1, so that there is an
embedding ϕ : S → n∈N Sn with each composite function
πn ◦ ϕ : S → Sn uniformly continuous.
Given a mapping ψ : A → S, let ψn = πn ◦ ψ.
A
ι|A
GG
ψ

ψn
22
ΩAV
ˆψn

S πn
GG Sn
The family ( ˆψn)n∈N induces a homomorphism ˆψ : ΩAV → n∈N Sn. Its
image lies in the closed subsemigroup T, whence it lifts to the required
continuous homomorphism ΩAV → S. It is uniformly continuous because
every continuous mapping from a compact metric space into another
metric space is uniformly continuous.
53 / 113
A subset of a metric space is said to be clopen if it is both closed
and open.
A metric space is said to be zero-dimensional if every open set is a
union of clopen subsets.
Proposition 5.4
Every pro-V semigroup is zero-dimensional.
Proof.
Let u be an element of the pro-V semigroup S. It suffices to show that
the open ball B (u) contains some clopen set which contains u.
For each v ∈ S \ B (u), let ϕv : S → Tv be a uniformly continuous
homomorphism into a semigroup from V such that ϕv (u) = ϕv (v). Then
Kv = ϕ−1
v ϕv (v) is a clopen set which contains v but not u. In particular,
the Kv form a clopen covering of the closed set S \ B (u), from which a
finite covering F can be extracted.
The union of the clopen sets in F is itself a clopen set K. Note that
S \ K is also clopen, contains u, and is contained in B (u).
54 / 113
For a mapping ϕ : S → T, let ker ϕ = {(u, v) : ϕ(u) = ϕ(v)}
be the kernel of ϕ.
Theorem 5.5
An A-generated profinite semigroup S is a continuous
homomorphic image of ΩAV if and only if it is a pro-V semigroup.
Corollary 5.6
Let S be a pro-V semigroup and suppose that ϕ : S → T is a
continuous homomorphism onto a finite semigroup. Then
T ∈ V.
55 / 113
Proof of Theorem 5.5.
(⇐) Apply Theorem 5.3.
(⇒) Let ϕ : ΩAV → S be an onto continuous homomorphism. We need
to show that S is residually in V.
Given distinct points s1, s2 ∈ S, since S is residually in S, there is an onto
uniformly continuous homomorphism ψ : S → T such that T ∈ S and
ψ(s1) = ψ(s2). Note that T is a finite continuous homomorphic image
of ΩAV. If we can show that S ∈ V, we will be done. In other words, it
suffices to consider the case where S is finite.
Since ϕ is continuous and ΩAV is compact, ϕ is uniformly continuous.
Hence, there is a positive integer n such that, for all u, v ∈ ΩAV,
d(u, v) < 2−n
⇒ ϕ(u) = ϕ(v).
In view of Proposition 4.6, it follows that the intersection ρ of the kernels
of the uniformly continuous homomorphisms ΩAV → V with V ∈ V and
|V | ≤ n is contained in ker ϕ. Hence, ϕ factors through the natural
homomorphism ΩAV → ΩAV/ρ. Since ΩAV/ρ belongs to V, so
does S.
56 / 113
Lemma 5.7 ([Num57, Hun88])
Let K be a clopen subset of a compact zero-dimensional metric semigroup S.
Then there is a continuous homomorphism ϕ : S → T into a finite semigroup
T such that K = ϕ−1
ϕ(K).
Proof.
We may define on S a syntactic congruence of K by
u σK v if ∀ x, y ∈ S1
(xuy ∈ K ⇔ xvy ∈ K).
It suffices to show that the classes of this congruence are open: then there are
only finitely many of them, so that S/σK is a finite semigroup, and the natural
mapping S → S/σK is a continuous homomorphism.
We show that, if lim un = u, then all but finitely many terms in the sequence
are σK -equivalent to u. Arguing by contradiction, otherwise, there is a
subsequence consisting of terms which fail this property. We may as well
assume that so does the original sequence.
For each n there are xn, yn ∈ S1
such that one, but not both, of the products
xnunyn and xnuyn lies in K. Again, by taking subsequences we may assume that
lim xn = x, lim yn = y (in S1
), and xnuyn /∈ K. Then
xuy = lim xnunyn = lim xnuyn must belong to both K and its complement.
57 / 113
A useful application of Lemma 5.7 is the following result, which
completes that of Proposition 5.4.
Theorem 5.8
A compact metric semigroup is profinite if and only if it is
zero-dimensional.
Proof.
(⇒) This follows from Proposition 5.4.
(⇐) Let S be a compact metric semigroup which is zero-dimensional.
We need to show that it is residually in S, that is that, for every pair s, t
of distinct points of S, there is a continuous homomorphism ϕ : S → T
in to a finite semigroup T such that ϕ(s) = ϕ(t).
Since S is a zero-dimensional metric space, there is some clopen subset
K such that s ∈ K and t /∈ K. By Lemma 5.7, there is a continuous
homomorphism ϕ : S → T into a finite semigroup T such that
K = ϕ−1
ϕ(K). In particular, we have ϕ(s) = ϕ(t), as required.
58 / 113
A language L ⊆ A+
is V-recognizable if its syntactic semigroup
belongs to V.
Theorem 5.9
A language L ⊆ A+
is V-recognizable if and only if the closure K = ι(L)
is open in ΩAV and ι−1
(K) = L. The latter condition is superfluous if
ι is injective and ι(A+
) is a discrete subset of ΩAV.
Proof.
(⇒) Use the universal property of ΩAV (Theorem 5.3).
(⇐) By Lemma 5.7, there is a continuous homomorphism ϕ : ΩAV → S
such that S ∈ V and K = ϕ−1
ϕ(K). Then ψ = ϕ ◦ ι is a homomorphism
A+
→ S such that ψ−1
ϕ(K) = ι−1
(K) = L and so L is
V-recognizable.
Theorem 5.9 implies that, as a topological space, ΩAV is the Stone
dual of the Boolean algebra of V-recognizable languages of A+
.
59 / 113
Theorem 5.10
A set S of V-recognizable languages over a finite alphabet A generates
the Boolean algebra of all such languages if and only if the clopen sets of
the form ι(L) (L ∈ S) suffice to separate points of ΩAV.
Proof.
(⇒) Let u, v ∈ ΩAV be distinct points. Then = d(u, v) is positive. Since
ΩAV is zero-dimensional (Proposition 5.4), there is a clopen subset K
containing u and contained in B (u), whence not containing v. By
Theorem 5.9, L = ι−1
(K) is V-recognizable. From the hypothesis, it follows
that L is a Boolean combination f (L1, . . . , Ln) of languages Li from S. By
Theorem 5.9 again, each set ι(Li ) is clopen. Since ι(X1 ∪ X2) = ι(X1) ∪ ι(X2)
and ΩAV \ ι(X) = ι(A+ \ X) for V-recognizable languages X, X1, X2 ⊆ A+
, we
have K = ι(L) = f (ι(L1), . . . , ι(Ln)). Hence at least one of the sets ι(Li ) must
contain exactly one of the points u and v.
(⇐) By Theorem 5.9, it suffices to show that the clopen sets of the form ι(L),
with L ⊆ A+
V-recognizable, generate the Boolean algebra of all clopen subsets
of ΩAV. This is a nice exercise on compactness.
60 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
61 / 113
Recall that a V-pseudoidentity is a formal equality u = v with
u, v ∈ ΩAV for some finite set A.
Recall also that, for S ∈ V, we write S |= u = v if
ϕ(u) = ϕ(v) for every continuous homomorphism
ϕ : ΩAV → S. In this case, we also say that u = v holds in S.
For a set Σ of V-pseudoidentities, let [[Σ]] denote the class of
all S ∈ V such that S |= u = v for every pseudoidentity u = v
from Σ.
For a subpseudovariety W of V, let pW : ΩAV → ΩAW be the
natural continuous homomorphism:
A
ιV
GG
ιW 33
ΩAV
pW:=ˆιW

ΩAW
62 / 113
Lemma 6.1
A pseudoidentity u = v, with u, v ∈ ΩAV, holds in every member
of a subpseudovariety W of V if and only if pW(u) = pW(v).
Theorem 6.2 ([Rei82])
A subclass W of V is a subpseudovariety if and only if it is of the
form [[Σ]] for some set Σ of V-pseudoidentities.
Usually, one takes V = S.
63 / 113
Proof of Theorem 6.2.
(⇐) This amounts to verifying that the property S |= u = v is preserved under
taking homomorphic images, subsemigroups and finite direct products, which
follows easily from the definitions.
(⇒) Fix a countably infinite set X and let Σ be the set of all pseudoidentities
u = v such that u, v ∈ ΩAV for some finite subset A of X and S |= u = v for
all S ∈ W. Then U = [[Σ]] is a subpseudovariety of V by the first part of the
proof, and it clearly contains W. We claim that U = W.
Let S ∈ U and choose an onto continuous homomorphism ϕ : ΩAU → S for
some finite subset A of X (cf. Theorem 5.3).
Consider the natural continuous homomorphisms pU
and pW. By Lemma 6.1 and the choice of Σ, we
have ker pW ⊆ ker pU and so there is a factorization
pU = ψ ◦ pW for some onto continuous homomorphism
ψ : ΩAW → ΩAU. Hence ϕ ◦ ψ : ΩAW → S is an
onto continuous homomorphism. Corollary 5.6 then implies
that S ∈ W since ΩAW is a pro-W semigroup by
Theorem 5.3.
ΩAV
pU
GG
pW

ΩAU
ϕ

ΩAW
ψ
``
S
64 / 113
To write pseudoidentities that are not identities, one needs to
construct some elements of ΩAS \ A+.
Lemma 6.3
Let S be a profinite semigroup, let s be an element of S, and let
k ∈ Z. Then the sequence of powers (sn!+k)n≥|k| converges. For
k = 0 the limit is an idempotent.
Proof.
Using Proposition 5.1, it suffices to consider the case where S is
finite, which is left as an exercise.
The limit lim sn!+k is denoted sω+k.
Note that sω+ksω+ = sω+k+ .
In particular, sω := sω+0 is an idempotent and sω−k and sω+k
are mutual inverses in the maximal subgroup containing the
idempotent sω.
65 / 113
Examples I
S = [[x = x]]
I = [[x = y]]
G = [[xω
= 1]]
Gp =?
A = [[xω+1
= xω
]]
Com = [[xy = yx]]
J = [[(xy)ω
= (yx)ω
, xω+1
= xω
]]
R = [[(xy)ω
x = (xy)ω
]]
L = [[y(xy)ω
= (xy)ω
]]
Sl = [[xy = yx, x2
= x]]
RZ = [[xy = y]]
B = [[x2
= x]]
N = [[xω
= 0]]
K = [[xω
y = xω
]]
D = [[yxω
= xω
]]
66 / 113
Examples II
Since there are uncountably many pseudovarieties of the form
AbP, where P is a set of primes, and one can show that all of
them admit a description of the form [[xy = yx, u = 1]]
[Alm95, Corollary 3.7.8], for some u ∈ Ω{x}S, we conclude
that Ω{x}S is uncountable.
Let P be an infinite set of primes and let p1, p2, . . . be an
enumeration of its elements, without repetitions.
Let uP be an accumulation point in Ω{x}S of the sequence
(xp1···pn )n.
AbP = [[xy = yx, uP = 1]].
Does the sequence (xp1···pn )n converge?
67 / 113
Examples III
To describe the pseudovariety Gp of all finite p-groups, we use
the following result, whose proof is similar to that of
Lemma 6.3.
Lemma 6.4
Let S be a profinite semigroup and s ∈ S. Then the sequence
(spn!
)n converges.
We let spω
= lim spn!
.
Gp = [[xpω
= 1]].
68 / 113
Examples IV
Exercise 6.5 (For those that know some group
theory)
Find, for each of the following pseudovarieties of groups, a single
pseudoidentity defining them:
(1) the pseudovariety Gp of all finite groups which have no
elements of order p (p being a fixed prime number);
(2) the pseudovariety Gnil of all finite nilpotent groups;
(3) the pseudovariety Gsol of all finite solvable groups.
69 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
70 / 113
N: finite nilpotent semigroups
Recall that N = [[xω
= 0]] = n≥1[[x1 · · · xn = 0]].
The proof depends on the following key result.
Lemma 7.1
Let S be a finite semigroup with n elements. Then, for every choice of
elements s1, . . . , sn ∈ S, there exist indices i, j such that 0 ≤ i < j ≤ n
and the following equality holds for all k ≥ 1:
s1 · · · sn = s1 · · · si (si+1 · · · sj )k
sj+1 · · · sn.
Proof.
Consider the n products pr = s1 · · · sr (r = 1, . . . , n). If they are all distinct,
then at least one of them, say pr , is idempotent and we may take i = 0, j = r.
Otherwise, there are indices i, j such that 1 ≤ i < j ≤ n and pi = pj , in which
case pi = pj = pi si+1 · · · sj = pi (si+1 · · · sj )k
.
71 / 113
Let ϕ : A+
→ S be a homomorphism into a semigroup S ∈ N, say
satisfying x1 · · · xn = 0. Then, all words of length at least n belong
to ϕ−1
(0) and for s ∈ S \ {0}, the words in the language
L = ϕ−1
(s) have length less than n, and so L is a finite set.
Thus, every N-recognizable language is either finite or cofinite.
To show that these are precisely the N-recognizable languages, it
suffices to show that every singleton language {w} ⊆ A+
is
N-recognizable.
Let n = |w| be the length of the word w. Consider the semigroup S
consisting of the words of A+
of length at most n together with a
zero element 0. The product of two words is the word resulting from
their concatenation if that word has length at most n and is 0
otherwise.1
Then S satisfies the identity x1 · · · xn = 0, for the
natural homomorphism ϕ : A+
→ S, that sends each letter to itself,
we have ϕ−1
(w) = {w}.
1
This amounts to“killing”the ideal of the semigroup A+
consisting of the
words of length greater than n, identifying all the elements in the ideal to a
zero. In semigroup theory, such a construction is called a Rees quotient.
72 / 113
Proposition 7.2
A language over a finite alphabet A is N-recognizable if and only if
it is finite or its complement in A+ is finite.
In view of Theorem 5.9, we deduce the following result:
Proposition 7.3
Let V be a pseudovariety of semigroups containing N. Then the
completion homomorphism ι : A+ → ΩAV is injective and A+ is a
discrete subspace of ΩAV. In particular, a language L ⊆ A+ is
V-recognizable if and only if its closure L in ΩAV is a clopen
subset.
73 / 113
Proof.
The injectivity of ι amounts to V satisfying no identity u = v with
u, v ∈ A+ distinct words. Indeed, Synt({u}) is nilpotent, whence it
belongs to V. Since 1u1 ∈ {u} while 1v1 /∈ {u}, we deduce that u
and v are not σ{u}-equivalent and so Synt({u}) |= u = v.
We may therefore identify each w ∈ A+ with ι(w) ∈ ΩAV.
For w ∈ A+, we have {w} = {w}, because ΩAV is a metric space.
Since {w} is V-recognizable, its closure {w} is an open subset
of ΩAV by Theorem 5.9. Hence A+ is a discrete subset
of ΩAV.
74 / 113
Proposition 7.4
The semigroup ΩAN is obtained by adding to A+ a zero element.
The open sets containing zero consist of zero together with a
cofinite subset of A+.2
Proof.
It suffices to observe that a non-eventually constant sequence
(wn)n of words of A+ is a Cauchy sequence with respect to the
metric dN if and only if lim |wn| = ∞. In the affirmative case, for
every homomorphism ϕ : A+ → S into S ∈ N, we have
lim ϕ(wn) = 0. Thus, all non-eventually constant Cauchy
sequences converge to the same point ot ΩAN, which is a zero.
The open subsets of ΩAN containing 0 have complement which is
a closed, whence compact, subset of A+. Since A+ is a discrete
subset of ΩAN, that complement must be finite. The converse is
clear.
2
This is known as the Alexandroff or one-point compactification, which in
general is obtained by adding one point and declaring the open sets containing
it to consist also of the complement of a compact subset of the original space.
75 / 113
K: finite semigroups satisfying es = e
Recall that K = [[xω
y = xω
]]. Note that
K =
n≥1
Kn where Kn = [[x1 · · · xny = x1 · · · xn]].
Let AN
denote the set of all right infinite words over A, i.e.,
sequences of letters.
Endow the set S = A+
∪ AN
with the operation
u · v =
uv if u ∈ A+
u otherwise
and the function d : S × S → R≥0 defined by d(u, v) = 2−r(u,v)
,
where r(u, v) is the length of the longest common prefix of u and v.
76 / 113
Proposition 7.5
The set S is a pro-K semigroup for the above operation and distance
function d. The unique continuous homomorphism ΩAK → S that sends each
letter a ∈ A to itself is an isomorphism.
Proof.
It is easy to check that the multiplication defined on S is associative and that d
is an totally bounded complete ultrametric.
Consider the set Sn consisting of all words of A+
of length at most n, endowed
with the operation
u · v =
uv if |uv| ≤ n
in(u) otherwise
where in(w) denotes the longest prefix of length at most n of the word w. This
operation is associative and Sn ∈ Kn. Moreover, every n-generated semigroup
from Kn is a homomorphic image of Sn. Hence Sn ΩAKn.
Note also that the mapping ϕn : S → Sn which sends each w ∈ S to in(w) is a
continuous homomorphism.
Hence, given two distinct points u and v from S, for n = r(u, v) + 1, the
mapping ϕn is a continuous homomorphism into a semigroup from K which
distinguishes u from v. Thus, S is a pro-K semigroup.
77 / 113
(. . . )
Consider next the unique continuous homomorphism ψ : ΩAK → S which maps
each letter a ∈ A to itself. Since K = n≥1 Kn, given distinct u, v ∈ ΩAK,
there exists a continuous homomorphism θ : ΩAK → Sn such that θ(u) = θ(v).
ΩAK
ψ
GG
θ

S
ϕn

Sn ΩAKn
µ
oo
The fact that the above diagram can always be completed by a homomorphism
µ shows that ψ(u) = ψ(v). Hence ψ is injective.
78 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
79 / 113
Implicit operations
Let n be a positive integer.
An n-ary implicit operation on pro-V semigroups is a
correspondence π associating to each pro-V semigroup S an
n-ary operation πS : Sn → S such that , for every continuous
homomorphism ϕ : S → T between pro-V semigroups, the
following diagam commutes:
Sn πS GG
ϕn

S
ϕ

Tn πT GG T,
i.e., ϕ πS (s1, . . . , sn) = πT ϕ(s1), . . . , ϕ(sn) for all
s1, . . . , s2 ∈ S.
Examples: the binary multiplication (s1, s2) → s1s2 and the
component projections (s1, . . . , sn) → si are implicit
operations. Composing implicit operations we also obtain
implicit operations.
80 / 113
If A and B are finite sets with the same cardinality n, then
ΩAV ΩBV. We denote by ΩnV any of them. Usually, we
identify ΩnV with ΩXn V, where Xn = {x1, . . . , xn} has
cardinality n.
To each w ∈ ΩnV, we may associate an n-ary implicit
operation πw on pro-V semigroups as follows:
for a pro-V semigroup S, given s1, . . . , sn ∈ S, let f : Xn → S
be the function defined by f (xi ) = si (i = 1, . . . , n);
let (πw )S (s1, . . . , sn) = ˆf (w) where ˆf completes the following
diagram:
Xn
ι GG
f
33
ΩnV
ˆf

S.
81 / 113
Proposition 8.1
1. For each w ∈ ΩnV, πw is indeed an n-ary implicit
operation on pro-V semigroups.
2. The correspondence w ∈ ΩnV → πw is injective and in
fact πw is completely characterized by the operations
(πw )S with S ∈ V.
82 / 113
Proof.
1. Let ϕ : S → T be a continuous homomorphism between two pro-V
semigroups and let s1, . . . , sn be elements of S. Let f : Xn → S be defined by
f (xi ) = si (i = 1, . . . , n). Then we have the following commutative diagram:
Xn
f

ϕ◦f
ι

ΩnV
ˆf
}} ϕ◦f
33
S ϕ
GG T
which shows that
ϕ (πw )S (f (s1), . . . , f (sn)) = ϕ ˆf (w) = ϕ ◦ f (w)
= (πw )T ϕ(f (s1)), . . . , ϕ(f (sn)) .
83 / 113
(. . . )
2. Let u, v ∈ ΩnV be two distinct elements. Then there exists a continuous
homomorphism ϕ : ΩnV → S into a semigroup S ∈ V such that ϕ(u) = ϕ(v).
Let si = ϕ(xi ) (i = 1, . . . , n). For w ∈ ΩnV, by definition of πw we have
(πw )S (s1, . . . , sn) = ϕ(w).
Since ϕ(u) = ϕ(v), we deduce that
(πu)S (s1, . . . , sn) = (πv )S (s1, . . . , sn)
and so, certainly πu = πv .
We identify w with πw .
Note that S ∈ V satisfies the V-pseudoidentity u = v if and only if
uS = vS .
We say that a pro-V semigroup S satisfies the V-pseudoidentity
u = v if uS = vS .
84 / 113
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
85 / 113
By an implicit signature we mean a set σ of implicit operations
(on S) which includes the binary operation of multiplication.
Example: κ = { · , ω−1}.
Given an implicit signature σ, each profinite semigroup S
becomes a natural σ-algebra in which each operation w ∈ σ is
interpreted as wS .
In particular, each ΩAV becomes a σ-algebra. The
σ-subalgebra generated by ι(A) is denoted Ωσ
AV.
For the minimum implicit signature σ, consisting only of
multiplication, we denote Ωσ
AV simply by ΩAV.3
A formal term constructed from the letters a ∈ A using the
operations from the implicit signature σ is called a σ-term
over A. Such σ-term w determines an element wV of Ωσ
AV by
evaluating the operations within Ωσ
AV.
3
The bar in the notation ΩAV comes from the fact ΩAV = ι(A+
) is dense
in ΩAV. This notation (without reference to V) was introduced by
Reiterman [Rei82].
86 / 113
The following result is an immediate consequence of
Theorem 5.3.
Proposition 9.1
The σ-algebra Ωσ
AV is a V-free σ-algebra freely generated by A in
the sense of the following universal property: for every mapping
ϕ : A → S into a semigroup S ∈ V, there is a unique
homomorphism ˆϕ of σ-algebras such that the following diagram
commutes:
A
ι GG
ϕ
33
Ωσ
AV
ˆϕ

S.
87 / 113
Examples:
Ωκ
AN = ΩAN;
for |A| ≥ 2, since ΩAK is uncountable, we have Ωσ
AK ΩAK
for every countable implicit signature σ;
Ωκ
AJ = ΩAJ [Alm95, Section 8.1];
Ωκ
AG is the free group freely generated by ι(A) = A;
Ωκ
ACR is the free completely regular (union of groups)
semigroup freely generated by ι(A) = A.
88 / 113
A key problem for the applications is to be able to solve the
word problem in the free σ-algebra Ωσ
AV: to find an algorithm,
if one exists, that given two σ-terms over A, determines
whether uV = vV.
If such algorithm exists, then we say that the word problem is
decidable; otherwise, we say that it is undecidable.
89 / 113
Examples:
The word problem for Ωκ
AN: two κ-terms coincide in Ωσ
AN if and
only if they are equal or they both involve the operation ω−1
.
The word problem for Ωκ
AG is well known: the operation ω−1
is
inversion in profinite groups, so all κ-terms can be effectively
reduced (over G) to κ-terms in which that operation is only applied
to letters; then use, in any order, the reduction rules aaω−1
→ 1 and
aω−1
a → 1 (a ∈ A) to obtain a canonical form for κ-terms over G;
two κ-terms are equal over G if and only if they have the same
canonical form.
Word problem for ΩAK: exercise.
The solution of the word problem for Ωκ
AJ = ΩAJ gives the
structure of ΩAJ [Alm95, Section 8.1].
The word problem for Ωκ
ACR has been solved by Kad’ourek and
Pol´ak [KP86].
The word problem for Ωκ
AA has been solved by
McCammond [McC01].
90 / 113
Part II
Separating words and regular
languages
91 / 113
Outline
σ-fullness
pro-V-metrics
92 / 113
A separation problem
Let V be a pseudovariety of semigroups.
Suppose that a regular language L ⊆ A+ and a word w ∈ A+
are given. How do we find out whether a proof that w /∈ L
exists using V-recognizable languages?
More precisely, we wish to decide whether, given such L and
w, there exists a V-recognizable language K ⊆ A+ such that
L ⊆ K and w /∈ K.
For instance, how do we determine whether there exists a
finite permutation automaton such that no word from L ends
in the same state as w does?
Another example of the same type of problem: is there some
integer n such that no word from L has the same subwords of
length at most n as w does?
93 / 113
Our problem sounds like a topological separation problem, and
indeed it admits such a formulation in the profinite world.
Proposition 10.1
Let V be a pseudovariety of semigroups, L ⊆ A+ a regular
language and w a word in A+. Then there is a V-recognizable
language K ⊆ A+ such that L ⊆ K and w /∈ K if and only if ιV(w)
does not belong to the closure of ιV(L) in ΩAV.
Proof.
By Proposition 5.4, the condition ιV(w) belongs to the closure ιV(L)
in ΩAV holds if and only if every clopen subset of ΩAV which contains
ιV(w) has nontrivial intersection with ιV(L). By Theorem 5.9, such
clopen subsets are precisely the sets of the form ιV(K) where K is a
V-recognizable subset of A+
. It remains to observe that, ιV(w) ∈ ιV(K)
and ιV(K) ∩ ιV(L) = ∅ if and only if w ∈ K and K ∩ L = ∅, which follows
from the facts that K = ι−1
V (ιV(K)) and L ⊆ ι−1
V (ιV(L)).
94 / 113
Note that, while ΩAV is in general uncountable, by
Theorem 5.9 it has only countably many clopen subsets, since
there are only that many V-recognizable subsets of A+ (for
instance since they are all recognized by finite automata).
An idea due to Pin and Reutenauer [PR91] in the case of the
pseudovariety G of all finite groups is to somehow“compute”
the closure of ιV(L) not in ΩAG but in the free group Ωκ
AG, or
even in A+.
Under the assumption of a conjectured property for the
pseudovariety G, they produced an algorithm for computing
the required closure, which solves our problem for G.
We proceed to introduce the required property in general,
returning later to their algorithm.
95 / 113
σ-fullness
For a subset L of A+, denote by clσ,V(L) and clV(L)
respectively the closure of ιV(L) in Ωσ
AV and in ΩAV.
Note that clσ,V(L) = clV(L) ∩ Ωσ
AV.
Denote by pV the natural continuous homomorphism
ΩAS → ΩAV.
Since ΩAS is compact and pV is a onto continuous mapping,
we always have the equality clV(L) = pV(clS(L)).
In general, for a continuous function f : S → T, and a subset
X of S, we have f (X) ⊆ f (X). The reverse inclusion also
holds if f is onto and S is compact.
We say that the pseudovariety V is σ-full if, for every regular
language L ⊆ A+, the following equality holds:
clσ,V(L) = pV(clσ,S(L)).
In other words, membership of w ∈ Ωσ
AV in clσ,V(L) is
witnessed by some w ∈ clσ,S(L) such that pV(w ) = w.
96 / 113
Examples:
The pseudovariety N is κ-full: for a regular language L ⊆ A+
and a κ-term w, wN ∈ clκ,N(L) if and only if w is a word
from L or w involves the operation ω−1 and L is infinite; in
the latter case, by compactness there is some κ-term v such
that vS ∈ clκ,S(L) \ A+ and so wN = 0 = pN(vS).
That the pseudovariety J is κ-full follows from the structure
theorem for ΩAJ.
The pseudovariety G is κ-full: the essential ingredient is a
seminal theorem of Ash [Ash91]; the details follow from
[AS00] and [Del01].
The pseudovariety Ab is κ-full [Del01].
97 / 113
The pseudovariety Gp is not κ-full: this follows from a weak
version of Ash’s theorem proved by Steinberg [Ste01] for Gp
together with fact that the conjunction of this weaker
property with κ-fullness implies that the pseudovariety is
defined by pseudoidentities in which both sides are given by
κ-terms [AS00]; however, such a definition does not exist
since, by a theorem of Baumslag [Bau65], the free group is
residually a finite p-group.
That the pseudovarieties A and R are κ-full has been proved
by JA-JCCosta-MZeitoun using the solution of the word
problems for Ωκ
AA [McC01]4 and Ωκ
AR [AZ07].
4
plus refinements from an alternative proof obtained by the same authors
including the fact that Ωκ
AA is closed for taking factors in ΩAA.
98 / 113
Outline
σ-fullness
pro-V-metrics
99 / 113
pro-V metrics
The same way we defined a pseudo-ultrametric on the free
semigroup A+ associated with a pseudovariety V, we may
define a pseudo-ultrametric on an arbitrary semigroup S: let
d(s1, s2) = 2−r(s1,s2)
,
where r(s1, s2) is the smallest cardinality of a semigroup
T ∈ V for which there is a homomorphism ϕ : S → T such
that ϕ(s1) = ϕ(s2).
Similar arguments show that d is indeed a pseudo-ultrametric
on S, with respect to which the multiplication in S is
uniformly continuous. If S is finitely generated, then the
completion ˆS is again a pro-V semigroup, but it may not be a
free pro-V semigroup.
The pseudo-ultrametric d is an ultrametric if and only if S is
residually in V.
Every homomorphism S → T into T ∈ V is uniformly
continuous.
100 / 113
Pro-H metric on groups
Traditionally, one denotes by H an arbitrary pseudovariety of
groups.
Because a group is highly symmetrical, the pro-H metric
structure looks similar everywhere.
Lemma 11.1
Let G be a group and consider the pro-H metric on G. Then, for
every u, v, w ∈ G, the equalities d(uw, vw) = d(u, v) = d(wu, wv)
hold. In particular, for > 0, we have Bε(u) = uBε(1) = Bε(1)u
and a subset X is open (respectively closed) if and only if so is
Xw. Moreover, for > 0, the ball B (1) is a clopen normal
subgroup of G such that G/B (1) ∈ H. A subgroup H is open if
and only if it contains some open ball B (1).
Proof.
This is a simple exercise.
101 / 113
For a subgroup H of a group G, denote by HG the largest
normal subgroup of G which is contained in H. It is given by
the formula
HG =
g∈G
g−1
Hg.
If we let G act on the set of right cosets of H in G by right
translation, then we obtain a homomorphism ϕ : G → SG/H
into the full symmetric group SG/H (of all permutations of the
set G/H) such that ϕ−1(id) = HG .
It follows that, if the index (G : H) of the subgroup H in G is
finite, then so is (G : HG ) and (G : HG ) is a divisor of
(G : H)!.
102 / 113
Lemma 11.2
A subgroup H of G is (cl)open in the pro-H metric if and only if
G/HG ∈ H.
Proof.
Suppose first that H is open. By Lemma 11.1, H contains a
normal subgroup K of G such that G/K ∈ H. Then K ⊆ HG and
so G/HG (G/K)/(HG /K) belongs to H. Conversely, if
G/HG ∈ H then HG is an open set, because the natural
homomorphism G → G/HG is (uniformly) continuous. Since H
contains HG , H is a union of cosets of HG , and so is its
complement. Hence H is clopen.
103 / 113
Another natural question is whether, for a subgroup H of G,
the intersection with H of an open subset of G in the pro-H
metric of G is also open in the pro-H metric of H.
In general, the answer is negative, but there are important
situations in which it is affirmative.
Example 11.3
Let G be the free group on two free generators a, b and consider
the homomorphism ϕ : G → S3 defined by ϕ(a) = (12) and
ϕ(b) = (13). Let K = ϕ−1(1) and let H = ϕ−1 (123) be the
inverse image of the subgroup of index 2. Then H is clopen in the
pro-Ab metric of G and K is clopen in the pro-Ab metric of H but
K is not clopen in the pro-Ab metric of G.
104 / 113
Note that, for pseudovarieties of groups K and H, K ∗ H
consists of all groups G which have a normal subgroup K such
that both K ∈ K and G/K ∈ H.5
If H ∗ H = H, then we say that H is closed under extension.
A condition for the answer to the above question to be
affirmative is drawn from the following result.
Lemma 11.4
Let H be a clopen subgroup of G in the pro-H metric of G and
suppose that U is a normal subgroup of H such that H/U ∈ H.
Then the normal subgroup UG of G is such that G/UG ∈ H ∗ H.
5
For those unfamiliar with semidirect products, take this as the definition of
K ∗ H and show that it is a pseudovariety of groups.
105 / 113
Proof.
Consider also the normal subgroup HG and let g ∈ G. By
Lemma 11.2, G/HG belongs to H. For each x ∈ HG , the
conjugate gxg−1 belongs to H and so the mapping
ϕg : HG → H/U which sends x to gxg−1U is a group
homomorphism. Moreover, for x ∈ HG , we have
x ∈ UG ⇔ x ∈ g−1
Ug for all g ∈ G
⇔ gxg−1
∈ U for all g ∈ G
⇔ ϕg (x) = 1 for all g ∈ G.
It follows that HG /UG embeds in a finite power of H/U and so
HG /UG ∈ H. The result now follows from the observation that
G/HG (G/UG )/(HG /UG ).
106 / 113
A first application of the preceding lemma is the following
answer to the above question.
Proposition 11.5
Suppose that H is closed under extension. Let H be a clopen
subgroup of G in the pro-H metric of G. Then a subset of H is
open in the pro-H metric of H if and only if it is open in the pro-H
metric of G.
Proof.
By Lemma 11.1, a subgroup L of H is open in the pro-H metric
of H if and only if it contains a normal subgroup U of H such that
H/U ∈ H. By Lemma 11.4, the normal subgroup UG of G is such
that U/UG ∈ H ∗ H = H. Hence U is open in the pro-H metric
of G by Lemma 11.2. Since L is a union of cosets of U, L is also
open in the pro-H metric of G.
107 / 113
In terms of the pro-H metrics, we obtain the following more
precise result.
Proposition 11.6
Suppose that H is closed under extension and G is a group
residually in H. Let H be a clopen subgroup of G in the pro-H
metric of G. Then the pro-H metric dH of H and the restriction
to H of the pro-H metric dG of G have the same Cauchy
sequences.
108 / 113
Proof.
Let d be the restriction of dG to H and let r be the corresponding partial
function H × H → N. Denote by d the pseudo-metric dH and by r the
corresponding partial function. We start by establishing the following function
inequalities:
r ≤ r ≤ (G : H) · r !. (1)
The first inequality in (1) follows from the observation that, if a
homomorphism from G into a member of H distinguishes two elements of H
then its restriction to H also distinguishes them. Suppose next that u, v ∈ H
and the homomorphism ϕ : H → K with K ∈ H are such that ϕ(u) = ϕ(v).
Let U = ϕ−1
(1). Then H/U embeds in K and, therefore, it belongs to H. By
Lemma 11.4, UG is a normal subgroup of G of finite index such that
G/UG ∈ H ∗ H = H and, by an earlier observation, (G : UG ) divides (G : U)!.
If we choose above K so that |K| is minimum, then (H : U) = r (u, v) and so,
since uUG = vUG ,
r(u, v) ≤ (G : UG ) ≤ (G : U)! = (G : H) · (H : U) ! = (G : H) · r (u, v) !
which proves (1).
109 / 113
. . .
From the first inequality in (1) we deduce that every Cauchy sequence
with respect to d is also a Cauchy sequence with respect to d. For the
converse, let f (n) = (G : H) · n !. Then f is an increasing sequence and
a simple calculation shows that, for every ε > 0,
d ≤ 2−f ( − log2 ε )
=⇒ d ≤ ε.
This implies that Cauchy sequences for d are also Cauchy sequences
for d .
110 / 113
Free products
A free product in a variety V of semigroups is given by two
homomorphisms ϕi : Si → F (i = 1, 2), with S1, S2, F ∈ V
such that, given any other pair of homomorphisms
ψi : Si → T, with T ∈ V, there exists a unique
homomorphism θ : F → T such that the following diagram
commutes:
F
θ
22
S1
ϕ1
oo
ψ1

S2
ϕ2
yy
ψ2
GG T
By the usual argument, if the free product exists, then it is
unique up to isomorphism.
111 / 113
Exercise 11.7
Show that, for every variety V and semigroups S1, S2 ∈ V, the free
product of S1 and S2 in V exists.
For semigroups S and T in a variety V, we say that S is a free
factor of T if there exists U ∈ V such that T is a free product
of S and U in V. Note that every semigroup is a free factor of
itself.
Exercise 11.8
Suppose that S is a free factor of T in the variety V generated by
a pseudovariety V. Show that:
1. the pseudo-metric dS
V and the restriction of the pseudo-metric
dT
V to S coincide;
2. the open sets in pro-V metric of S are the intersection with S
of the open sets of T in the pro-V metric of T.
112 / 113
Section 12
References
113 / 113
[ABR92] D. Albert, R. Baldinger, and J. Rhodes, The identity problem for
finite semigroups (the undecidability of), J. Symbolic Logic 57
(1992), 179–192.
[AE03] J. Almeida and A. Escada, Semidirect products with the
pseudovariety of all finite groups, Proceedings of the International
Conference Words, Languages and Combinatorics (Kyoto, March,
2000) (Singapore) (M. Ito and T. Imaoka, eds.), World Scientific,
2003, pp. 1–21.
[Alm95] J. Almeida, Finite semigroups and universal algebra, World
Scientific, Singapore, 1995, English translation.
[AS00] J. Almeida and B. Steinberg, On the decidability of iterated
semidirect products and applications to complexity, Proc. London
Math. Soc. 80 (2000), 50–74.
[AS03] K. Auinger and B. Steinberg, On the extension problem for partial
permutations, Proc. Amer. Math. Soc. 131 (2003), 2693–2703.
[Ash87] C. J. Ash, Finite semigroups with commuting idempotents, J.
Austral. Math. Soc., Ser. A 43 (1987), 81–90.
113 / 113
[Ash91] , Inevitable graphs: a proof of the type II conjecture and
some related decision procedures, Int. J. Algebra Comput. 1
(1991), 127–146.
[AZ07] J. Almeida and M. Zeitoun, An automata-theoretic approach of the
word problem for ω-terms over R, Theor. Comp. Sci. 370 (2007),
131–169.
[Bau65] G. Baumslag, Residual nilpotence and relations in free groups, J.
Algebra 2 (1965), 271–282.
[BS73] J. A. Brzozowski and I. Simon, Characterizations of locally testable
events, Discrete Math. 4 (1973), 243–271.
[Del01] M. Delgado, On the hyperdecidability of pseudovarieties of groups,
Int. J. Algebra Comput. 11 (2001), 753–771.
[Eil76] S. Eilenberg, Automata, languages and machines, vol. B, Academic
Press, New York, 1976.
[HMPR91] K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash’s type II
theorem, profinite topology and Malcev products. Part I, Int. J.
Algebra Comput. 1 (1991), 411–436.
113 / 113
[HR91] K. Henckell and J. Rhodes, The theorem of Knast, the PG=BG and
Type II Conjectures, Monoids and Semigroups with Applications
(Singapore) (J. Rhodes, ed.), World Scientific, 1991, pp. 453–463.
[Hun88] R. P. Hunter, Certain finitely generated compact zero-dimensional
semigroups, J. Austral. Math. Soc., Ser. A 44 (1988), 265–270.
[KP86] Jiˇri Kad’ourek and Libor Pol´ak, On the word problem for free
completely regular semigroups, Semigroup Forum 34 (1986),
127–138.
[KR65] K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime
decomposition theorem for finite semigroups and machines, Trans.
Amer. Math. Soc. 116 (1965), 450–464.
[McC01] J. McCammond, Normal forms for free aperiodic semigroups, Int.
J. Algebra Comput. 11 (2001), 581–625.
[MP71] R. McNaughton and S. Papert, Counter-free automata, MIT Press,
Cambridge, MA, 1971.
[MP84] S. W. Margolis and J.-E. Pin, Varieties of finite monoids and
topology for the free monoid, Proc. 1984 Marquette Semigroup
Conference (Milwaukee), Marquette University, 1984, pp. 113–129.
113 / 113
[MP87] , Inverse semigroups and varieties of finite semigroups, J.
Algebra 110 (1987), 306–323.
[Num57] K. Numakura, Theorems on compact totally disconnetced
semigroups and lattices, Proc. Amer. Math. Soc. 8 (1957),
623–626.
[Pin95] J.-E. Pin, BG=PG: A success story, Semigroups, Formal Languages
and Groups (Dordrecht) (J. Fountain, ed.), vol. 466, Kluwer, 1995,
pp. 33–47.
[PR91] J.-E. Pin and C. Reutenauer, A conjecture on the Hall topology for
the free group, Bull. London Math. Soc. 23 (1991), 356–362.
[PS85] J.-E. Pin and H. Straubing, Monoids of upper triangular matrices,
Semigroups: structure and universal algebraic problems
(Amsterdam) (G. Poll´ak, ed.), North-Holland, 1985, pp. 259–272.
[Rei82] J. Reiterman, The Birkhoff theorem for finite algebras, Algebra
Universalis 14 (1982), 1–10.
[Sch65] M. P. Sch¨utzenberger, On finite monoids having only trivial
subgroups, Inform. and Control 8 (1965), 190–194.
[Sim75] I. Simon, Piecewise testable events, Proc. 2nd GI Conf. (Berlin),
Lect. Notes in Comput. Sci., vol. 33, Springer, 1975, pp. 214–222.
113 / 113
[Ste01] B. Steinberg, Inevitable graphs and profinite topologies: some
solutions to algorithmic problems in monoid and automata theory,
stemming from group theory, Int. J. Algebra Comput. 11 (2001),
25–71.
[Sti73] P. Stiffler, Extension of the fundamental theorem of finite
semigroups, Advances in Math. 11 (1973), 159–209.
113 / 113