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 / 70
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 / 70
Part I
Relatively free profinite semigroups
3 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
4 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
11 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
19 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
33 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
48 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 profinite semigroup. Then
T ∈ V.
55 / 70
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 / 70
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 / 70
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 → 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 / 70
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 / 70
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 / 70
Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
61 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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 / 70
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
lements 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 / 70
Section 7
References
70 / 70
[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.
[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.
[Ash91] , Inevitable graphs: a proof of the type II conjecture and
some related decision procedures, Int. J. Algebra Comput. 1
(1991), 127–146.
[BS73] J. A. Brzozowski and I. Simon, Characterizations of locally testable
events, Discrete Math. 4 (1973), 243–271.
70 / 70
[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.
[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.
[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.
[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.
70 / 70
[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.
[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.
[Sti73] P. Stiffler, Extension of the fundamental theorem of finite
semigroups, Advances in Math. 11 (1973), 159–209.
70 / 70