Proﬁnite 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 / 332
Abstract
Finite semigroups appear naturally in Computer Science, namely as syntactic semigroups of regular
languages, transition semigroups of ﬁnite automata, or as ﬁnite recognizing devices on their own.
Eilenberg’s correspondence theorem gives a general framework for the classiﬁcation 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 ﬁnite semigroups is given and one
wishes to decide whether a given ﬁnite semigroup is a homomorphic image of a subsemigroup of a
ﬁnite product of members of R. Since such a problem is often undecidable, special techniques have
been devised to handle special cases. Relatively free proﬁnite 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 proﬁnite semigroups and to explore two
topics in which there have been signiﬁcant 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:
Part 1 Relatively free proﬁnite semigroups. (1 lecture)
Reference:
[1] J. Almeida, Proﬁnite 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.
Part 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.
Part 3 Relatively free proﬁnite semigroups and Symbolic Dynamics. (2 lectures)
Reference:
[1] (see above).
2 / 332
Part I
Relatively free proﬁnite semigroups
3 / 332
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 / 332
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∗ deﬁned 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 / 332
Theorem 1.1
The following conditions are equivalent for a language L over a
ﬁnite alphabet A:
(1) L is regular;
(2) L is recognized by some ﬁnite automaton;
(3) L is recognized by some ﬁnite complete deterministic
automaton;
(4) the syntactic monoid A∗/σL on A∗ is ﬁnite;
(5) L is recognized by some homomorphism ϕ : A∗ → M into a
ﬁnite 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 / 332
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 ﬁnite monoid, D = J
*0
a *ab
*ba b
*1
7 / 332
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 / 332
Dyck language: L∞ = n≥0 Ln, where L0 = {1},
Ln+1 = (aLnb)∗.
Recognition by inﬁnite 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 / 332
Exercise 1.3
Consider the transition semigroup S of the following inﬁnite 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 inﬁnite
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 / 332
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 / 332
A variety of languages is a correspondence V associating with
each ﬁnitely generated free monoid A∗ a set V(A∗) of
languages over the ﬁnite 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 ﬁnite
monoids which is closed under taking homomorphic images,
submonoids, and ﬁnite direct products.
12 / 332
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 ﬁnite alphabet A;
to a pseudovariety V, associate the variety of languages V
such that, for each ﬁnite alphabet A, V(A∗) consists of the
languages L ⊆ A∗ such that M(L) ∈ V.
13 / 332
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 ﬁnite
monoids and we want to determine an algorithm to decide
whether a given ﬁnite monoid M belongs to the pseudovariety
V(R) generated by R.
14 / 332
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 / 332
Examples of pseudovarieties:
S: all ﬁnite semigroups
I: all singleton (trivial)
semigroups
G: all ﬁnite groups
Gp: all ﬁnite p-groups
A: all ﬁnite aperiodic
semigroups
Com: all ﬁnite
commutative
semigroups
J: all ﬁnite J -trivial
semigroups
R: all ﬁnite R-trivial
semigroups
L: all ﬁnite L-trivial
semigroups
Sl: all ﬁnite semilattices
RZ: all ﬁnite right-zero
semigroups
B: all ﬁnite bands
N: all ﬁnite nilpotent
semigroups
K: all ﬁnite semigroups in
which idempotents are left
zeros
D: all ﬁnite semigroups in
which idempotents are right
zeros
16 / 332
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 ﬁnite alphabet is star free if and only if its
syntactic semigroup is ﬁnite and aperiodic.
17 / 332
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 ﬁnite alphabet is piecewise testable if and only if
its syntactic semigroup is ﬁnite 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 ﬁnite alphabet is locally testable if and only if
its syntactic semigroup S is ﬁnite and a local semilattice (i.e.,
eSe is a semilattice for every idempotent e ∈ S).
18 / 332
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 / 332
Definition 3.1
We say that a pseudovariety V is decidable if there is an algorithm
which, given a ﬁnite semigroup S as input, produces as output, in
ﬁnite 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 ﬁnite set Q
generated by a ﬁnite set A of transformations of Q ;
→ transition semigroup of a ﬁnite automaton (Q, A, δ, I, F);
by means of a presentation.
Diﬀerent ways of describing S may lead to diﬀerent
complexity results, when such an algorithm exists.
20 / 332
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 / 332
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 ﬁnite
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 / 332
Let S be a ﬁnite 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 identiﬁcation 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 ﬁnite semigroups
whose blocks lie in V.
23 / 332
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 ﬁnite direct products.
Given a ﬁnite 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 eﬀectively check whether eSe ∈ V.
Hence one can eﬀectively check whether S ∈ LV.
24 / 332
But, the most interesting operators are deﬁned 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 ﬁnite 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 ﬁnite direct product, then V(C)
consists of all divisors of elements of C.
25 / 332
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 / 332
Definition 3.11
The Mal’cev product V m W of two pseudovarieties V and W is
the smallest pseudovariety containing all ﬁnite 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 ﬁnite 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 / 332
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 / 332
Some examples of results on ﬁnite 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 ﬁnite semigroups in
which idempotents are central) [Alm95]
5. ESl = Sl ∗ G = Sl m G = Inv (the pseudovariety generated by
all ﬁnite 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 / 332
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 ﬁnite 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 / 332
This brings us to the following basic question:
Question 3.16
For the operators which were deﬁned above in terms of generators,
do they preserve decidability?
Theorem 3.17 (Albert, Baldinger & Rhodes’1992
[ABR92])
There exists a ﬁnite 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 / 332
The pseudovariety U is deﬁned 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 inﬁnite 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 / 332
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 / 332
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 / 332
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 preﬁx“pseudo”.
35 / 332
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 ﬁnite number of balls of
any given positive radius is said to be totally bounded.
36 / 332
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 ﬁnitely 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 / 332
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 / 332
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 Hausdorﬀ
completion of X.
39 / 332
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) deﬁnes 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 deﬁned;
(f) ﬁnally, 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 / 332
Note that ι(X) is dense in ˆX.
In particular, we may consider the Hausdorﬀ 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 / 332
We endow each ﬁnite 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 / 332
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 / 332
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 suﬃciently 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 suﬃciently large n, d(u, ι(un)) < 2−m
and
d(v, ι(vn)) < 2−m
.
Hence d(un, vn) = d(ι(un), ι(vn)) ≥ 2−m
for all suﬃciently large n.
It follows that every S ∈ V with |S| < m fails the identity un = vn
and, therefore, also the pseudoidentity u = v.
44 / 332
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 / 332
Recall that a metric space is compact if every sequence admits
some convergent subsequence. Equivalently, every covering by
open subsets contains a ﬁnite 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 / 332
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 ﬁnite subset of X such that
X = x∈Fm
B2−m (x) and consider an arbitrary sequence (un)n in X.
For inﬁnitely many indices n, the un belong to the same B2−1 (x1). Let k1
be the ﬁrst of these indices. Similarly, among the remaining such indices,
there are inﬁnitely many n such that the un belong to the same B2−2 (x2).
We let k2 be the ﬁrst 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 / 332
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 / 332
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 proﬁnite semigroup we mean a pro-S semigroup.
49 / 332
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 deﬁne 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 / 332
Note that the sequence (Sn)n∈N may be chosen so that there
is a ﬁnite bound on the number of generators of the Sn if and
only if S is ﬁnitely generated in the sense that there is a ﬁnite
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 ﬁnitely generated.
51 / 332
For a ﬁnite 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 satisﬁed, where ϕ : A → T is an arbitrary
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 ﬁnite set A, the metric
semigroup ΩAV is a pro-V semigroup freely generated by A via the
mapping ι|A.
52 / 332
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 / 332
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 suﬃces 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
ﬁnite 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 / 332
For a mapping ϕ : S → T, let ker ϕ = {(u, v) : ϕ(u) = ϕ(v)}
be the kernel of ϕ.
Theorem 5.5
An A-generated proﬁnite 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 ﬁnite semigroup. Then
T ∈ V.
55 / 332
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 ﬁnite continuous homomorphic image
of ΩAV. If we can show that S ∈ V, we will be done. In other words, it
suﬃces to consider the case where S is ﬁnite.
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 / 332
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 ﬁnite semigroup
T such that K = ϕ−1
ϕ(K).
Proof.
We may deﬁne on S a syntactic congruence of K by
u σK v if ∀ x, y ∈ S1
(xuy ∈ K ⇔ xvy ∈ K).
It suﬃces to show that the classes of this congruence are open: then there are
only ﬁnitely many of them, so that S/σK is a ﬁnite semigroup, and the natural
mapping S → S/σK is a continuous homomorphism.
We show that, if lim un = u, then all but ﬁnitely 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 / 332
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 proﬁnite 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 ﬁnite 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 ﬁnite semigroup T such that
K = ϕ−1
ϕ(K). In particular, we have ϕ(s) = ϕ(t), as required.
58 / 332
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 superﬂuous 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 / 332
Theorem 5.10
A set S of V-recognizable languages over a ﬁnite alphabet A generates
the Boolean algebra of all such languages if and only if the clopen sets of
the form ι(L) (L ∈ S) suﬃce 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 suﬃces 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 / 332
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 / 332
Recall that a V-pseudoidentity is a formal equality u = v with
u, v ∈ ΩAV for some ﬁnite 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 / 332
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 / 332
Proof of Theorem 6.2.
(⇐) This amounts to verifying that the property S |= u = v is preserved under
taking homomorphic images, subsemigroups and ﬁnite direct products, which
follows easily from the deﬁnitions.
(⇒) Fix a countably inﬁnite set X and let Σ be the set of all pseudoidentities
u = v such that u, v ∈ ΩAV for some ﬁnite subset A of X and S |= u = v for
all S ∈ W. Then U = [[Σ]] is a subpseudovariety of V by the ﬁrst 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 ﬁnite 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 / 332
To write pseudoidentities that are not identities, one needs to
construct some elements of ΩAS \ A+.
Lemma 6.3
Let S be a proﬁnite 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 suﬃces to consider the case where S is
ﬁnite, 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 / 332
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 / 332
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 inﬁnite 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 / 332
Examples III
To describe the pseudovariety Gp of all ﬁnite p-groups, we use
the following result, whose proof is similar to that of
Lemma 6.3.
Lemma 6.4
Let S be a proﬁnite semigroup and s ∈ S. Then the sequence
(spn!
)n converges.
We let spω
= lim spn!
.
Gp = [[xpω
= 1]].
68 / 332
Examples IV
Exercise 6.5 (For those that know some group
theory)
Find, for each of the following pseudovarieties of groups, a single
pseudoidentity deﬁning them:
(1) the pseudovariety Gp of all ﬁnite groups which have no
elements of order p (p being a ﬁxed prime number);
(2) the pseudovariety Gnil of all ﬁnite nilpotent groups;
(3) the pseudovariety Gsol of all ﬁnite solvable groups.
69 / 332
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 / 332
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 ﬁnite 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 / 332
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 ﬁnite set.
Thus, every N-recognizable language is either ﬁnite or coﬁnite.
To show that these are precisely the N-recognizable languages, it
suﬃces 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 satisﬁes 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 / 332
Proposition 7.2
A language over a ﬁnite alphabet A is N-recognizable if and only if
it is ﬁnite or its complement in A+ is ﬁnite.
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 / 332
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 / 332
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
coﬁnite subset of A+.2
Proof.
It suﬃces 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 aﬃrmative 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 of Ω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 ﬁnite. The converse is
clear.
2
This is known as the Alexandroﬀ or one-point compactiﬁcation, 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 / 332
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 inﬁnite 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 deﬁned by d(u, v) = 2−r(u,v)
,
where r(u, v) is the length of the longest common preﬁx of u and v.
76 / 332
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 deﬁned 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 preﬁx 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 / 332
(. . . )
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 / 332
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 / 332
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 diagram commutes:
Sn πS GG
ϕn

S
ϕ

Tn πT GG T,
i.e., ϕ πS (s1, . . . , sn) = πT ϕ(s1), . . . , ϕ(sn) for all
s1, . . . , sn ∈ 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 / 332
If A and B are ﬁnite 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 deﬁned by f (xi ) = si (i = 1, . . . , n);
let (πw )S (s1, . . . , sn) = ˆf (w) where ˆf is a continuous
homomorphism completing the following diagram:
Xn
ι GG
f
33
ΩnV
ˆf

S.
81 / 332
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 / 332
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 deﬁned 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 / 332
(. . . )
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 deﬁnition 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 satisﬁes the V-pseudoidentity u = v if and only if
uS = vS .
We say that a pro-V semigroup S satisﬁes the V-pseudoidentity
u = v if uS = vS .
84 / 332
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 / 332
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 proﬁnite 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 a σ-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 / 332
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 / 332
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 / 332
A key problem for the applications is to be able to solve the
word problem in the free σ-algebra Ωσ
AV: to ﬁnd an algorithm,
if one exists, that given two σ-terms over A, determines
whether uV = vV.
If such an algorithm exists, then we say that the word problem
is decidable; otherwise, we say that it is undecidable.
89 / 332
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 proﬁnite groups, so all κ-terms can be eﬀectively
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 / 332
Part II
Separating words and regular
languages
91 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
92 / 332
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 ﬁnd 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
ﬁnite 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 / 332
Our problem sounds like a topological separation problem, and
indeed it admits such a formulation in the proﬁnite 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 / 332
Corollary 10.2
Let V be a pseudovariety containing N. If w is a word in A+ and
L ⊆ A+ is a regular language, then w and L can be separated by a
V-recognizable language if and only if w /∈ L.
Proof.
By Proposition 7.3, ι embeds A+ in ΩAV as a discrete subspace,
meaning that every subset is open. Hence, if w belongs to the
closure L of L in ΩAV, then w ∈ L.
More directly, in case N ⊆ V, the language {w} is
V-recognizable and therefore there is a V-recognizable
language containing w and disjoint from L if and only if
w /∈ L.
Note that the condition N ⊆ V is equivalent to V satisfying
some pseudoidentity of the form xω+n = xn, where n is a
positive integer.
95 / 332
A refined separation separation problem
Even for pseudovarieties V containing N, the separation
problem becomes nontrivial if we wish instead to separate two
regular languages by a V-recognizable language.
The following result can be proved basically by the same
argument as presented for the proof of Proposition 10.1,
taking additionally into account that ΩAV is compact. The
details are left as an exercise.
Proposition 10.3
Let V be a pseudovariety of semigroups and L1, L2 ⊆ A+ regular
languages. Then there is a V-recognizable language K ⊆ A+ such
that L1 ⊆ K and L2 ∩ K = ∅ if and only if the closures of ιV(L1)
and ιV(L2) in ΩAV are disjoint sets.
96 / 332
In the case of A, Henckell has constructed an algorithm,
working directly in a ﬁnite semigroup which recognizes
simultaneously two given regular languages, which decides
whether they may be separated by a star-free
language [Hen88].
An idea due to Pin and Reutenauer [PR91] in the case of the
pseudovariety G of all ﬁnite 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.
97 / 332
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.
In particular, for w ∈ A+, we have ι(w) ∈ clV(L) if and only if
ι(w) ∈ clσ,V(L).
Denote by pV the natural continuous homomorphism
ΩAS → ΩAV.
Since ΩAS is compact and pV is an 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.
98 / 332
σ-fullness
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.
99 / 332
Theorem 10.4 ([AS00a])
Let V be a pseudovariety, A a ﬁnite alphabet and σ an implicit signature such
that the following conditions hold:
(1) V is σ-full;
(2) the word problem for Ωσ
AV is decidable;
(3) σ is recursively enumerable;
(4) V is recursively enumerable;
(5) for each operation in σ, there is an algorithm to compute it in any given
ﬁnite semigroup.
Then it is decidable whether, given a regular language L ⊆ A+
and a
pseudoword w ∈ Ωσ
AV, we have w ∈ clσ,V(L).
Proof sketch.
Enumerate the pairs (w, L) for which w ∈ clσ,V(L) holds using the assumptions
(1)–(3). To enumerate those for which the condition fails, enumerate 4-tuples
(ϕ, ψ, X, w) where ϕ : ΩAS → S and ψ : ΩAS → T are onto continuous
homomorphisms with S ∈ S and T ∈ V, X ⊆ S, and w ∈ Ωσ
AS are such that
X × {ψ(w)} ∩ Im(ϕ × ψ) = ∅ and output the corresponding pairs
(w, ϕ−1
(L) ∩ A+
). This requires the assumptions (4) and (5).
100 / 332
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 inﬁnite; 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 [Alm95, Section 8.2].
The pseudovariety G is κ-full: the essential ingredient is a
seminal theorem of Ash [Ash91]; the details follow from
[AS00a] and [Del01].
The pseudovariety Ab is κ-full [Del01].
101 / 332
The pseudovariety Gp is not κ-full: this follows from a weak
version of Ash’s theorem proved by Steinberg [Ste01] for Gp
together with the fact that the conjunction of this weaker
property with κ-fullness implies that the pseudovariety is
deﬁned by pseudoidentities in which both sides are given by
κ-terms [AS00a] (cf. Proposition 11.1); however, such a
deﬁnition does not exist since, by a theorem of
Baumslag [Bau65], the free group is residually a ﬁnite 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 reﬁnements from an alternative proof obtained by the same authors
including the fact that Ωκ
AA is closed for taking factors in ΩAA.
102 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
103 / 332
Separation in σ-algebras
Let σ be an implicit signature.
Let V be a pseudovariety of semigroups.
Note that, if two regular languages K, L ⊆ A+ have disjoint
closures in ΩAV then they also have disjoint closures in Ωσ
AV.
If the converse also holds, then we say that V is weakly
σ-reducible for the separation problem.
This is a special case of a more general weak reducibility
property introduced in [AS00a]. The property is considered in
general for an arbitrary system of equations, the present case
being that of the equation x = y.
Naturally, there is also a stronger form of that property, which
we are not considering in these lectures. For a σ-full
pseudovariety, the two versions of the property are equivalent
[AS00a, AS00b].
104 / 332
Among others, the following pseudovarieties are known to be
weakly κ-reducible for the separation problem:
G [Ash91];
CR [AT01];
Gp, with p prime [Ste01];
A [JA-JCCosta-MZeitoun];
R [AS01];
J (follows from the solution of the word problem for ΩAJ
[Alm95, Section 8.2]);
LSl [CT04].
105 / 332
Say that a pseudovariety V is σ-equational if it admits a
deﬁnition by pseudoidentities involving only σ-operations.
Such pseudoidentities are also called σ-identities.
Proposition 11.1 ([AS00a])
If a pseudovariety V is weakly σ-reducible for the separation
problem and σ-full, then V is σ-equational.
106 / 332
Proof.
Let Σ be the set of all σ-identities which are valid in V. Clearly
V ⊆ [[Σ]].
Let S be a ﬁnite semigroup S that satisﬁes Σ. By Reiterman’s
Theorem 6.2, to show that S ∈ V, it suﬃces to establish that
S satisﬁes every pseudoidentity which is valid in V. Consider such
a pseudoidentity u = v, say with u, v ∈ ΩAS, and let ϕ : ΩAS → S
be a continuous homomorphism. We claim that ϕ(u) = ϕ(v).
Let K = ϕ−1(ϕ(u)) ∩ A+ and L = ϕ−1(ϕ(v)) ∩ A+. Note that,
since u ∈ clS(K), v ∈ clS(L), and pV(u) = pV(v), we have
clV(K) ∩ clV(L) = ∅. Since V is weakly σ-reducible for the
separation problem, there is some w ∈ clσ,V(K) ∩ clσ,V(L). Since
V is σ-full, there are w1 ∈ clσ,S(K) and w2 ∈ clσ,S(L) such that
pV(w1) = w = pV(w2). Hence w1 = w2 is a pseudoidentity
from Σ, which therefore is valid in S. Hence, we have
ϕ(u) = ϕ(w1) = ϕ(w2) = ϕ(v), which establishes the claim.
107 / 332
Theorem 11.2 ([AS00a])
Let V be a pseudovariety, A a ﬁnite alphabet and σ an implicit
signature such that the following conditions hold:
(1) V is σ-full;
(2) V is weakly σ-reducible for the separation problem;
(3) the word problem for Ωσ
AV is decidable;
(4) σ is recursively enumerable;
(5) V is recursively enumerable;
(6) for each operation in σ, there is an algorithm to compute it in
any given ﬁnite semigroup.
Then it is decidable whether two given regular languages
L1, L2 ⊆ A+ may be separated by a V-recognizable language
K ⊆ A+.
108 / 332
Proof.
Using property (5), we may enumerate the pairs (L1, L2) of regular languages
over A+
that may be separated by V-recognizable languages, by simply
enumerating triples (L1, L2, ϕ), with ϕ : A+
→ S a homomorphism onto an
arbitrary semigroup from V, and test whether ϕ separates L1 and L2. In the
aﬃrmative case, output (L1, L2).
To enumerate the pairs that may not be separated, we use the assumption (2)
plus Proposition 10.3, which guarantees that, if L1 and L2 cannot be separated
by a V-recognizable language, then there is some w ∈ clσ,V(L1) ∩ clσ,V(L2)
which witnesses the non-separability. Each condition w ∈ clσ,V(Li ) may be
eﬀectively tested by Theorem 10.4 and the candidates for witnesses may be
recursively enumerated by (4). We may thus proceed as follows:
enumerate all triples (L1, L2, w) with L1, L2 ∈ A+
regular languages and
w ∈ Ωσ
AV;
for each such triple, test whether w ∈ clσ,V(Li ) (i = 1, 2);
output the pairs (L1, L2) which pass the test as non-separable by
V-recognizable languages.
109 / 332
The algorithms described in Theorems 10.4 and 11.2 are
purely theoretical, being unusable in practice.
Thus, it is worth, particularly in cases where the decidability
of the separation property is already guaranteed by
Theorem 11.2, to ﬁnd eﬃcient algorithms to test separability.
110 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
111 / 332
pro-V metrics
The same way we deﬁned a pseudo-ultrametric on the free
semigroup A+ associated with a pseudovariety V, we may
deﬁne 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 ﬁnitely 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.
112 / 332
Let V be a pseudovariety of semigroups, and let σ be an
implicit signature.
Considering the members of V as σ-algebras under the natural
interpretation of the operations from σ, since the
homomorphisms are the same, V is still a pseudovariety
of σ-algebras.
We may deﬁne a pseudo-ultrametric on a σ-algebra S similarly
to the semigroup case: let
dσ
(s1, s2) = 2−rσ(s1,s2)
where rσ(s1, s2) is the smallest cardinality of a member T ∈ V
for which there is a homomorphism ϕ : S → T of σ-algebras
such that ϕ(s1) = ϕ(s2).
113 / 332
The delicate point here is that, while continuous semigroup
homomorphisms between proﬁnite semigroups respect implicit
operations, and in particular so do semigroup homomorphisms
between ﬁnite semigroups, semigroup homomorphisms
between arbitrary σ-algebras may not be homomorphisms of
σ-algebras.
Example: let U1 be two-element semilattice, which the
multiplicative subsemigroup of Z consisting of 0, 1; consider
the mapping ϕ : ΩAN → U1 that maps A+ to 1 and
everything else to 0. Then ϕ is a semigroup homomorphism
but not a homomorphism of κ-algebras.
114 / 332
Proposition 12.1
For a pseudovariety V and an implicit signature σ, the completion
of Ωσ
AV with respect to the pseudo-ultrametric dσ is ΩAV, both
metrically and algebraically.
Proof.
Since the algebraic structure is inherited by extension of uniformly
continuous operations, it suﬃces to show that, for u, v ∈ Ωσ
AV,
dσ
(u, v) = d(u, v), where d is the completion metric on ΩAV.
By Proposition 4.6, d(u, v) = 2−r
, where r is the smallest cardinality of a
member T ∈ V for which there exists a continuous homomorphism
ϕ : ΩAV → T such that ϕ(u) = ϕ(v). Since the restriction of ϕ to Ωσ
AV
is a homomorphism of σ-algebras which separates u from v, it follows
that rσ
(u, v) ≤ r. On the other hand, by the universal property of ΩAV
and since we interpret σ-operations naturally, every homomorphism of
σ-algebras Ωσ
AV → T ∈ V extends uniquely to a continuous
homomorphism ΩAV → T. Hence rσ
(u, v) = r.
115 / 332
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 12.2
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.
116 / 332
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
ﬁnite, then so is (G : HG ) and (G : HG ) is a divisor of
(G : H)!.
117 / 332
Lemma 12.3
A subgroup H of G is (cl)open in the pro-H metric if and only if
G/HG ∈ H.
Proof.
Suppose ﬁrst that H is open. By Lemma 12.2, 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.
118 / 332
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 aﬃrmative.
Example 12.4
Let G be the free group on two free generators a, b and consider
the homomorphism ϕ : G → S3 deﬁned 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.
119 / 332
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
aﬃrmative is drawn from the following result.
Lemma 12.5
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 deﬁnition of
K ∗ H and show that it is a pseudovariety of groups.
120 / 332
Proof.
Consider also the normal subgroup HG and let g ∈ G. By
Lemma 12.3, 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 ﬁnite power of H/U and so
HG /UG ∈ H. The result now follows from the observation that
G/HG (G/UG )/(HG /UG ).
121 / 332
A ﬁrst application of the preceding lemma is the following
answer to the above question.
Proposition 12.6
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 12.2, 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 12.5, 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 12.3. Since L is a union of cosets of U, L is also
open in the pro-H metric of G.
122 / 332
In terms of pro-H metrics, we obtain the following more
precise result.
Proposition 12.7
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.
123 / 332
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 ﬁrst 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 12.5, UG is a normal subgroup of G of ﬁnite 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).
124 / 332
(. . . )
From the ﬁrst 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 .
125 / 332
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.
126 / 332
Exercise 12.8
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 12.9
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.
127 / 332
Theorem 12.10
Let H be a ﬁnitely generated subgroup of a ﬁnitely generated free
group G in the variety generated by the extension-closed
pseudovariety H and suppose that H is a free factor of a clopen
subgroup of G in the pro-H metric. Then the following hold:
1. the pro-H metric dH of H has the same Cauchy sequences as
the restriction of the pro-H metric dG ;
2. the completion of H with respect to dG is a free pro-H group.
128 / 332
Proof.
We may as well assume that H is not the trivial pseudovariety for,
otherwise, the result is obvious. Hence H contains some cyclic
group of prime order Z/pZ. Since H is closed under extension, it
follows that Gp ⊆ H for some prime p. Since the free group is
residually a ﬁnite p-group by a result of Baumslag [Bau65], we may
therefore assume that G is an absolutely free group. By the
Nielsen-Schreier Theorem, the subgroup H is also an absolutely
free group. By Proposition 12.1, the completion of H with respect
to the metric dH is a free pro-H group. Since, by Proposition 12.7
and Exercise 12.9, the Cauchy sequences of H are the same with
respect to both metrics dH and dG , the completion of H with
respect to both metrics is the same metric group and so it is a free
pro-H group.
129 / 332
The following corollaries will be useful later.
Corollary 12.11
Let H be an extension-closed pseudovariety of groups and let G be
a ﬁnitely generated free group in the variety generated by H. If the
ﬁnitely generated subgroup H is a free factor of a clopen subgroup
of G in the pro-H metric, then H is closed in that metric.
The following result is known as the subgroup theorem in the
theory of proﬁnite groups. For simplicity, it is presented here only
in the ﬁnitely generated case, although the proof could be
extended to the general case.
Corollary 12.12
Let H be a clopen subgroup of a ﬁnitely generated free pro-H
group G, where H is an extension-closed pseudovariety of groups.
Then H is itself a free pro-H group.
130 / 332
Proof of Corollary 12.11.
Since the pro-H metric of a clopen subgroup is the induced metric, we may as
well assume that H is a free factor of G. Let (hn)n be a sequence of elements
of H and suppose that it converges in G to an element g. Suppose H is
another subgroup of G such that G is the free product of H and H . Then, by
considering the identity mapping on H and sending H to 1 we obtain an onto
homomorphism ϕ : G → H which is obviously continuous with respect to the
pro-H metrics of G and H. Hence (hn)n already converges in H, namely to
ϕ(g). Since the metrics dH and dG have the same Cauchy sequences in H by
Theorem 12.10, the limit must be the same in both cases, and so g ∈ H. This
shows that H is closed in the pro-H metric of G.
Proof of Corollary 12.12.
Let A be a ﬁnite free generating set for G. Let G be the subgroup of G
discretely generated by A. Then G is a free group over A in the variety
generated by H and it is a dense subgroup of G. Let H = H ∩ G . Then H is
a clopen subgroup of G in the pro-H topology of G . Since H is open, H is
dense in H. Hence H is the completion of H with respect to the metric dG .
Applying Theorem 12.10 to the free factor H of itself, it follows that H is a
free pro-H group.
131 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
132 / 332
The free group and inverse automata
Let now G be a free group on a ﬁnite set A. To each ﬁnite subset X of G we
associate a ﬁnite inverse automaton as follows.6
For each reduced group word representative w of an element of X,
consider a linear graph with directed edges labeled by the successive
letters of w, the edge appearing in the direction of left-to-right reading of
w if the corresponding generator appears with exponent 1 and in the
opposite direction if the exponent is −1. Thus the label of the undirected
path which traverses the graph in the direction of left-to-right reading
of w is w.
Glue these graphs together by identifying their ends to a single vertex v0
which is the unique initial and ﬁnal state of the automaton.
Fold edges so that the resulting automaton becomes inverse in the sense
that the transformations deﬁned by the labels are partial bijections. This
can be done by applying the following procedure, in an arbitrary order,
until it no longer applies: whenever we encounter two edges with the
same label leaving from the same state or arriving at the same state, we
identify them.
6
See [Sta83, MSW01, KM02] for details and further references.
133 / 332
Example 1
Let G be the free group on the free generators a, b, c and let
X = {ab−1c−1a, a−1b−1ac−1a, bc−1a}. Then the sequence of pictures in Figure 1
describes the construction of the folded inverse automaton associated with X.
◦ ◦
◦ ◦
◦ ◦
a b
c
a
a b a
c
a
b
c
a
◦◦
◦ a
b
c
aa
b
a
c a
b
c
a
◦
◦ a
b
caa
b
a c a
b
c
a
◦
◦
a
b
c
b
a c a
b
c
a
◦
◦
ab
c
a
b
a c
b
c
ab
c a
b
a
b
Figure: The folding procedure
134 / 332
The automaton resulting from the above procedure is reduced
in the sense that it has a unique initial state which is
simultaneously the unique ﬁnal state, every state is accessible
from it (through an undirected path), and there is no state of
degree 1 other than possibly the initial and ﬁnal state.
The set of reduced group words recognized by the automaton
is precisely the subgroup X generated by X.
Moreover, this automaton is unique up to isomorphism and it
depends only on the subgroup X and not on the speciﬁc
generating set X. Thus, for a ﬁnitely generated subgroup H of
the free group G on a set A, we will denote its automaton
by A(H).
Conversely, a given ﬁnite reduced inverse automaton A over
the alphabet A recognizes a ﬁnitely generated subgroup of the
free group on A whose associated automaton is A. This
subgroup is the fundamental group of the underlying graph.
135 / 332
The following result summarizes the properties of the construction
of the automaton associated with a ﬁnitely generated subgroup of
a free group.
Theorem 13.1
The correspondence which maps each ﬁnitely generated subgroup
H of the free group G on the set A to its automaton A(H),
constructed from a ﬁnite generating set of H, has the following
properties:
1. the automaton A(H) is eﬀectively constructible and does not
depend on the generating set but only on H;
2. the correspondence deﬁnes a bijection between the set of all
ﬁnitely generated subgroups of G and the set of all ﬁnite
reduced inverse automata with input alphabet A.
136 / 332
Example 2
We recall the procedure to compute the fundamental group
of a connected labeled directed graph with a root vertex,
namely to exhibit a ﬁnite generating set for that subgroup.
First, choose a generating tree, that is a maximal subgraph
whose underlying undirected graph is a tree. Note that every
vertex of the original graph is on the tree. To each edge e
which is not on the chosen tree, associate the group word
which is obtained by reading the label of the (undirected)
path which goes from the root along the tree to the beginning
vertex of e, then follows e, and then returns to the root
along the tree. The set of all words associated in this way
to the edges which are not on the tree generates a subgroup
of the free group on the labels which is called the fundamental
group of the labeled graph. This procedure is shown
here for the inverse automaton obtained in the preceding example.
The resulting generating set for the same subgroup,
namely the subgroup recognized by the inverse automaton,
is {a−1
ca−1
ba, ba−1
ba, ab−1
a−1
ba}. The set thus obtained
freely generates the subgroup. This also gives a procedure
to compute free generators for the subgroup of a free group
generated by a given ﬁnite set of group words.
ab
a
b
a c
b
ab
a
b
a c
b
ab
a
b
a c
b
a−1
· c · a−1
ba
ab
a
b
a c
b
b · a−1
ba
ab
a
b
a c
b
a · b−1
a−1
ba
137 / 332
We proceed to explore some other relationships between inverse
automata and ﬁnitely generated subgroups of free groups.
Let A and B be two reduced inverse automata with the same input
alphabet A. A morphism f : A → B is a function which maps states of A
to states of B, sending the initial state of A to that of B, in such a way
that the action of A is respected:
if q is a state of A, a ∈ A ∪ A−1
, and qa is deﬁned, then f (q)a is
also deﬁned and f (q)a = f (qa).
Note that if such a morphism exists then it is unique.
Proposition 13.2
Let G be a free group and let H and K be ﬁnitely generated subgroups
of G. Then H ⊆ K if and only if there is an automaton morphism from
A(H) into A(K). Moreover, if the morphism is injective then H is a free
factor of K.
138 / 332
Proof.
Suppose ﬁrst that there exists an automaton morphism A(H) → A(K). A
reduced group word w representing an element of H labels a successful path
in A(H). By transforming this path by the morphism, we obtain a successful
path in A(K), which shows that w also represents an element from K. Hence
H ⊆ K.
Conversely, suppose that H ⊆ K. We may choose ﬁnite sets X and Y of
reduced words such that X = H and X ∪ Y = K. Then, the construction of
A(H) and A(K) proceeds from sets of linear automata in which the ﬁrst is
contained in the second. This implies that every identiﬁcation which is made to
obtain A(H) will also occur in the construction of A(K). Hence there is a
morphism A(H) → A(K).
Suppose next that there is an injective morphism A(H) → A(K). Choose for
A(H) a generating tree. Its image in A(K) is still a tree and so it can be
expanded to a generating tree of A(K). Hence there is a free generating set for
K which contains a free generating set for H and this is equivalent to H being
a free factor of K.
139 / 332
Let A be an inverse automaton. A congruence on A is an
equivalence relation ∼ on the state set of A which is compatible
with the action of the input alphabet A:
if q1, q2 are states, a ∈ A ∪ A−1, q1a, q2a are both deﬁned,
and q1 ∼ q2, then q1a ∼ q2a.
We may then consider the quotient automaton A/∼, whose states
are the ∼-classes of states of A and such that the action of A is
given by (q/∼)a = (qa)/∼. Note that A/∼ is an inverse
automaton.
140 / 332
Lemma 13.3
Let H and K be ﬁnitely generated subgroups of the free group on
a ﬁnite set A and suppose that H ⊆ K. For each state p, choose a
reduced word up which labels a path in A(H) from the initial state
to p. Then the congruence ∼H,K on A(H) determined by the
kernel of the unique morphism ϕ : A(H) → A(K) satisﬁes the
following condition:
for all states p, q, p ∼H,K q if and only if upu−1
q ∈ K. (2)
Moreover, if L is the fundamental group of the quotient automaton
A(H)/∼H,K , then H ⊆ L and L is a free factor of K.
141 / 332
Proof.
If upu−1
q ∈ K, then up and u−1
q label paths in A(K) from the
initial-ﬁnal state to the states ϕ(p) and ϕ(q). Since A(K) is an
inverse automaton which recognizes K, it follows that
ϕ(p) = ϕ(q), that is p ∼H,K q. Conversely, if p ∼H,K q, then
ϕ(p) = ϕ(q) and so the reduced form of upu−1
q labels a loop at
the initial-ﬁnal state in A(K), that is upu−1
q ∈ K. This proves
condition (2). The last part of the statement of the lemma follows
from Proposition 13.2.
142 / 332
Proposition 13.4
Let H be a ﬁnitely generated subgroup of the ﬁnitely generated
free group G on a ﬁnite set A, which is endowed with the pro-V
topology. Then the following hold:
1. if H is a clopen normal subgroup then A(H) is a permutation
automaton whose transition monoid is isomorphic to G/H and
belongs to V;
2. H is clopen if and only if A(H) is a permutation automaton
whose transition monoid belongs to V.
143 / 332
Proof.
By Lemma 12.3, if H is a clopen normal subgroup then G/H ∈ V. The
Cayley graph of the ﬁnite group G/H with respect to A can be viewed as
a reduced inverse automaton which recognizes H as the set of reduced
group words which label loops at the vertex 1. Hence it is isomorphic to
A(H) and A(H) is a (complete) permutation automaton. The states in
the Cayley graph are precisely the cosets of H, on which the input
alphabet acts by right translation. Hence the transition monoid is
isomorphic to G/H and it belongs to V.
Next we assume only that H is clopen. By Lemma 12.3, HG is a clopen
normal subgroup. The quotient automaton A(HG )/∼HG ,H embeds
in A(H). Since A(HG ) is a complete automaton by (1), so is its quotient
A(HG )/∼HG ,H . Since A(H) is a reduced inverse automaton, it follows
that A(H) is also a permutation automaton as there is no room in
A(HG )/∼HG ,H to add vertices or edges. The transition monoid of A(H)
is therefore a quotient of that of A(HG ), which is isomorphic to G/HG
by (1), and therefore it belongs to V.
144 / 332
(. . . )
Conversely, suppose that A(H) is a permutation automaton whose
transition monoid M belongs to V and consider the natural
homomorphism ϕ : G → M and K = ϕ−1
(1). Then K consists of all
reduced words which map every state of A(H) to itself while H consists
of all reduced words which map the state 1 to itself. Hence K ⊆ H and
H is clopen since K is clopen by Lemma 12.3.
145 / 332
A simple application of Proposition 13.4 is the following theorem
due to M. Hall [Hal50] in a paper which ﬁrst introduced proﬁnite
topologies on free groups.
Theorem 13.5
Every ﬁnitely generated subgroup of a free group G on a ﬁnite
set A is closed in the proﬁnite metric of G.
146 / 332
Proof.
Let H be a ﬁnitely generated subgroup of G. If H = G, then of course H
is closed. Otherwise, it suﬃces to show that, for every reduced word
g ∈ G \ H, there is a clopen subgroup which contains H but not g.
Consider the automaton A(H) and add to it, starting from the
initial-ﬁnal state, a linear automaton which reads g. By applying the
folding procedure, we end up with an inverse automaton, which may not
be reduced, in which the end state of the added linear automaton is not
identiﬁed to the initial-ﬁnal state. Each generator a ∈ A determines in
this automaton a partial permutation of the state set. Now, every partial
permutation of a ﬁnite set may be completed to a full permutation and
we choose such a completion for each generator a ∈ A. This leads to a
permutation automaton B in which A(H) embeds. By Proposition 13.4,
the fundamental group K of B is a clopen subgroup of G. By
Proposition 13.2, K contains H. On the other hand, g /∈ K since in B
the reduced word g does not label a loop at the initial-ﬁnal state.
147 / 332
Note 13.6
An alternative proof of Theorem 13.5 is obtained as follows.
Complete the automaton A(H) of the given ﬁnitely generated
subgroup of G to a permutation automaton B, with the same
initial-ﬁnal state. By Proposition 13.4, the fundamental group K
of B is a clopen subgroup. By Proposition 13.2, H is contained
in K. By Corollary 12.11, since G is extension closed, H is closed.
148 / 332
Example 3
In Example 1 we obtained the ﬁrst inverse automaton in Figure 2
1
2
3
45
ab
a
b
a c
b
1
2
3
45
ab
a
b
a c
b
a
a
b
b
c
c
c
c
Figure: An inverse automaton and one of its completions
which gives the partial permutations deﬁned in the table on the left and one of their
possible completions to permutations in the table on the right
1 2 3 4 5
a 2 − − 1 3
b 3 − 2 − 4
c − − − 3 −
1 2 3 4 5
a 2 4 5 1 3
b 3 1 2 5 4
c 1 2 4 3 5
and the corresponding permutation automaton in Figure 2. This permutation
automaton determines a clopen subgroup K, in the proﬁnite metric of the free group,
of which the original subgroup is a free factor.
149 / 332
More generally, we say that a ﬁnitely generated subgroup H of the free
group G on the ﬁnite set A is V-extendible if A(H) can be extended to a
permutation automaton whose transition monoid belongs to V. In such
an extension, both states and transitions may be added.
Lemma 13.7
The ﬁnitely generated subgroup H of the free group G on a ﬁnite set A is
V-extendible if and only if there is a clopen subgroup K of G, in the
pro-V metric of G, such that the congruence ∼H,K on A(H) is the
equality.
Proof.
If H is V-extendible, then there is a permutation automaton B containing
A(H), with the same initial-ﬁnal state, whose transition monoid belongs
to V. By Proposition 13.4, the fundamental group K of B is clopen in
the pro-V metric of G. Then A(H) embeds in A(K) and so, by deﬁnition
of the congruence ∼H,K (cf. Lemma 13.3), this congruence is the equality
relation on the state set of A(H). The converse is proved similarly.
150 / 332
By deﬁnition of pro-V metric, the closure of a subgroup of a group
G is the intersection of the clopen subgroups that contain it. In
the case of ﬁnitely generated subgroups of a ﬁnitely generated free
group, we can use the previous results to obtain a more precise
statement.
Proposition 13.8
Let H be a ﬁnitely generated subgroup of the free group G on a
ﬁnite set A, which is endowed with the pro-V metric, and let H be
the closure of H in G. Then the following hold:
1. there is a clopen subgroup K of G such that ∼H,H coincides
with ∼H,K ;
2. there is a smallest V-extendible subgroup containing H,
namely the subgroup ˜H such that A(˜H) is the image of A(H)
in A(H);
3. H ⊆ ˜H ⊆ H and ˜H is a free factor of H.
151 / 332
Proof.
By Proposition 13.2, for each clopen subgroup K containing H,
there is a morphism A(H) → A(K), which determines a
congruence on A(H). The intersection ∼ of all such congruences
is still a congruence on A(H). Since the automaton A(H) is ﬁnite,
the intersection ∼ involves only ﬁnitely many congruences and so
A(H)/∼ is the largest quotient of A(H) which embeds in a
permutation automaton of a clopen subgroup. The fundamental
group of A(H)/∼ is therefore a ﬁnitely generated subgroup L
containing H which is a free factor of the clopen subgroup K,
whose automaton A(K) is the smallest permutation automaton in
which A(L) embeds and which has a transition monoid in V. This
proves the proposition.
152 / 332
The following result reduces the computation of ˜H (and therefore also
the question as to whether H is V-extendible) to the membership
problem of the pro-V closure H.
Proposition 13.9
Let G be a ﬁnitely generated free group, endowed with the pro-V metric,
and let H be a given ﬁnitely generated subgroup of G. If the membership
problem for H is decidable then one can eﬀectively compute the smallest
V-extendible subgroup ˜H of G containing H.
Proof.
By Proposition 13.8, it suﬃces to compute the congruence ∼H,H on the
automaton A(H). By condition (2) of Lemma 13.3, this congruence can
be computed by the choice of a label uq for a path from the initial-ﬁnal
state to each state q by using the solution of the membership problem
for H.
Thus, one may concentrate on the membership problem for the closure
subgroup H.
153 / 332
Proposition 13.8 is insuﬃcient to guarantee the existence of an algorithm
to compute the closure H of a given ﬁnitely generated subgroup H. In
case V is an extension-closed pseudovariety, we obtain some more precise
results.
Theorem 13.10
Let H be a ﬁnitely generated subgroup of a ﬁnitely generated free group,
which is endowed with the pro-V metric for an extension-closed
pseudovariety V. The following conditions are equivalent:
1. H is closed;
2. H is V-extendible;
3. H is a free factor of a clopen subgroup.
Proof.
By Proposition 13.8, (1) implies H = ˜H = H which yields (2) since ˜H is
V-extendible. Condition (2) implies (3) by Proposition 13.2. Finally, (3)
implies (1) by Corollary 12.11.
154 / 332
Corollary 13.11
Under the hypotheses of Theorem 13.10, ˜H = H.
Exercise 13.12
Let G be a ﬁnitely generated free group and endow it with the
pro-V metric. Let H be a ﬁnitely generated subgroup of G. Prove
the following:
1. for every g ∈ G, the automaton A(g−1Hg) is obtained by
modifying A(H) as follows: if the initial-ﬁnal state of A(H) is
q0 then set that of A(g−1Hg) to be the state q0g;
2. H is V-extendible if and only if all its conjugates are
V-extendible;
3. H is closed (respectively open) if and only if all its conjugates
have the same property.
155 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
156 / 332
Relative invertibility of endomorphisms
Given a continuous endomorphism ϕ of ΩnM, we denote by
M(ϕ) the n × n-matrix over the proﬁnite ring ˆZ whose
(i, j)-coordinate is the image of ϕ(xi ) of the i-th generator
of ΩnM under the unique continuous homomorphism
ΩnM → ˆZ which maps xj to 1 and all other generators to 0.
The determinant and trace of the matrix M(ϕ) are also called,
respectively, the determinant and trace of ϕ and are denoted
det ϕ and tr ϕ.
Exercise 14.1
Let M be a proﬁnite monoid. Show that m ∈ M is invertible if and
only if m is right invertible, if and only if m is left invertible, if and
only if mω = 1.
157 / 332
For a metric semigroup S, denote by End S the monoid of
continuous endomorphisms of S.
For a pseudovariety V of monoids and w ∈ ΩnM, denote by
wV the restriction of the implicit operation w to V.
For ϕ ∈ End ΩnM, denote by ϕV the continuous
endomorphism of ΩnV induced by ϕ, which maps the
generator xi to (ϕ(xi ))V.
Say that ϕ is V-invertible if ϕV is invertible in End ΩnV.
Proposition 14.2
A continuous endomorphism ϕ of ΩnM is V-invertible if and only
if ΩnV is generated by the set {ϕV(xi ) : i = 1, . . . , n}.
158 / 332
Proof.
Let M be the (closed) submonoid of ΩnV generated by
{ϕV(xi ) : i = 1, . . . , n}.
Suppose ﬁrst that ϕ is V-invertible. Then (ϕω)V = (ϕV)ω is the
identity mapping on ΩnV. Given u ∈ ΩnV, letting w = ϕω−1
V (u),
we conclude that
u = ϕV(w) = ϕV wΩAV(x1, . . . , xn) = wΩAV ϕV(x1), . . . , ϕV(xn) ,
where the last equality is justiﬁed since implicit operations on V
commute with continuous homomorphisms between pro-V
semigroups. Since w is the limit of a sequence of words, it follows
that u ∈ M, which shows that M = ΩnV.
159 / 332
(. . . )
Conversely, suppose that M = ΩnV. Given u ∈ ΩnV, there exists a
sequence of words (wn)n such that
u = lim
n→∞
(wn)ΩnV ϕV(x1), . . . , ϕV(xn) = lim
n→∞
ϕV(wn).
Since ΩnM is a compact metric space, we may assume that the
sequence (wn)n converges to some w ∈ ΩnM. For such an implicit
operation w, we have ϕV(w) = u. In particular, for each generator
xi there exists vi ∈ ΩnM such that xi = ϕV(vi ). Let ψ be the
continuous endomorphism of ΩnM which maps xi to vi . Then the
composite continuous endomorphism ϕV ◦ ψV ﬁxes the generators
xi and, therefore it is the identity mapping of ΩnV. Hence ϕV is
invertible.
160 / 332
Let Ab denote the pseudovariety of all ﬁnite Abelian groups.
Let Am denote the pseudovariety of all ﬁnite Abelian groups
of exponent m.
Proposition 14.3
The following conditions are equivalent for a continuous
endomorphism ϕ of ΩnM and a prime integer p:
1. ϕ is Gp-invertible;
2. ϕ is Ap-invertible;
3. det ϕ is not divisible by p.
161 / 332
Proof.
Since Ap ⊆ Gp, clearly (1)⇒(2). On the other hand, (2)⇔(3)
follows from elementary Linear Algebra since ΩnAp is the additive
reduct of the n-dimensional vector space over the ﬁeld Z/pZ. We
prove (2)⇒(1) by contraposition and so we assume that ϕ is not
Gp-invertible. Then, by Proposition 14.2, the set
{ϕGp (xi ) : i = 1, . . . , n} generates a proper closed subgroup H
of ΩnGp. Since ΩnGp is a proﬁnite group, it follows that H is
contained in some proper clopen subgroup K of ΩnGp. Hence
there is a continuous homomorphism ψ : ΩnGp → F onto a ﬁnite
p-group F such that ψ(H) is the trivial subgroup. We may assume
that ψ is the restriction mapping ΩnGp → ΩnAp, from which we
deduce that ϕAp is the trivial endomorphism of ΩnAp and,
therefore, it is not Ap-invertible.
162 / 332
Exercise 14.4
Show that the following conditions are equivalent for an element u
of the ring ˆZ:
1. u is multiplicatively invertible (or a unit);
2. no prime integer divides u;
3. u is invertible in each p-adic completion Zp.
Hence, if u ∈ Z, then u is invertible in ˆZ if and only if u = ±1.
163 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
164 / 332
Here is a ﬁrst result with an algorithmic ﬂavour towards the
computation of the closure of a ﬁnitely generated subgroup of the
free group.
Proposition 15.1
Let V be a non-trivial extension-closed pseudovariety of groups and
let G be a ﬁnitely generated free group which is endowed with the
pro-V metric. Suppose that a ﬁnitely generated subgroup H of G
is not dense in G and let ϕ : G → F be a homomorphism onto
F ∈ V such that ϕ(H) F. Then one can compute from ϕ a
closed ﬁnitely generated free factor L of some clopen subgroup K
of G such that A(L) is a quotient of the automaton A(H).
165 / 332
Proof.
Put K = ϕ−1
ϕ(H) . Then K is a clopen subgroup of ﬁnite index in G.
Consider the congruence ∼H,K on the inverse automaton A(H) and let L
be the ﬁnitely generated subgroup of G such that A(L) A(H)/∼H,K .
By Lemma 13.3, L is a free factor of K. By Corollary 12.11, L is a closed
subgroup of G.
It remains to argue that all constructions are eﬀective. Given the ﬁnite
group F and the onto homomorphism ϕ, and the free generating set A
of G, consider the right action of A on the set F/ϕ(H) of all right cosets
of ϕ(H). This deﬁnes a permutation automaton which is precisely the
automaton A(K). Given H by means of a ﬁnite set of generators, one
may also construct its automaton A(H). The construction of the
quotient automaton A(H)/∼H,K then can be made from the knowledge
of both automata A(H) and A(K). The quotient automaton in turn
determines the closed subgroup L, for which we may exhibit a ﬁnite set of
generators.
166 / 332
Definition 15.2
We say that a pseudovariety V of groups has decidable denseness if,
given a ﬁnite set A and a ﬁnite subset B of the free group G on A, it is
decidable whether B generates a dense subgroup in the pro-V metric
of G.
The following theorem summarizes and completes some of the above
results.
Theorem 15.3
Let V be an extension-closed pseudovariety of groups. Let H be a ﬁnitely
generated subgroup of the ﬁnitely generated free group G and let H be
the closure of H in the pro-V metric of G.
1. The group H is ﬁnitely generated and a free factor of a clopen
subgroup of G.
2. The automaton A(H) is a quotient of A(H).
3. If V is recursively enumerable and has decidable denseness then
there is an algorithm to construct a ﬁnite set of generators of H.
167 / 332
Proof.
By Corollary 13.11, the subgroup H coincides with ˜H, which in turn is
ﬁnitely generated by Proposition 13.8. The remainder of the statement
of (1) is a direct consequence of Theorem 13.10 while (2) now also
follows from Proposition 13.8.
It remains to prove (3). Let A be a set of free generators for G. Here is
how the algorithm proceeds. Since V has decidable denseness, we ﬁrst
check whether H is dense in G. In the aﬃrmative case, we have found H
to be G. In the negative case, we know that there is some
homomorphism ϕ : G → F onto some group F in V such that
ϕ(H) G. Since V is recursively enumerable and G is ﬁnitely generated,
we may successively enumerate candidates to such homomorphisms until
we ﬁnd one with this property.
Once such a homomorphism is found, by Proposition 15.1 one can
compute from ϕ a ﬁnite set A = {v1, . . . , vr } of free generators for a
closed free factor L of some clopen subgroup K of G such that A(L) is a
quotient A(H)/∼1 of A(H).
168 / 332
(. . . )
If {w1, . . . , wm} is a set of generators for H, then we may express each wi
as a group word wi (v1, . . . , vr ) on the groups words vj . Consider the
subgroup H of the free group G on the set A generated by
{w1, . . . , wm}. The mapping which sends each free generator vj to itself,
viewed as a group word in the given free generators of G, extends
uniquely to a continuous homomorphism ψ : G → G which is an
isomorphism with L. Since the induced metric on L is the pro-V metric
of L by Theorem 12.10, ψ : G → L is a continuous isomorphism with
respect to the corresponding pro-V topologies. Since ψ preserves the
index of subgroups, as well as quotients for normal subgroups, ψ is an
isomorphism of topological groups. Since L is closed in G by
Corollary 12.11, the problem of computing the closure of H in G is thus
reduced to the computation of the closure of H in G .
169 / 332
(. . . )
Now, if we apply the above procedure to H as a subgroup of G , either
H is dense in G , in which case we conclude that H = L, or we obtain a
free factor L of a clopen subgroup K of G such that
H ⊆ L ⊆ K G and AA (L ) is a quotient of AA (H ). It follows that
H ⊆ ψ(L ) ⊆ ψ(K ) L, ψ(L ) is a free factor of the clopen subgroup
ψ(K ) (of G). Moreover, it is easy to see that A ψ(L ) is the quotient
of A(H) by a congruence ∼2. Since H ⊆ ψ(L ) L, the congruence ∼2
is properly contained in ∼1.
Thus, applying the above procedure recursively, in a ﬁnite number of
steps we must obtain an aﬃrmative answer to the question as to whether
the current subgroup is a free factor of the current free group. At that
stage, the closure will be computed and then it is a matter of substituting
back the free generators to their expressions in the original alphabet A to
obtain H.
170 / 332
Corollary 15.4
Let V be an extension-closed pseudovariety of groups with
decidable denseness. Then it is decidable whether a given ﬁnitely
generated subgroup of a ﬁnitely generated free group is
V-extendible.
Since the closure of a ﬁnitely generated subgroup is computed
by successively taking closed factors of clopen subgroups,
combining with Theorem 12.10, we also obtain the following
result.
Corollary 15.5
Let H be a ﬁnitely generated subgroup of a ﬁnitely generated free
group G and suppose that H is closed with respect to the pro-V
metric of G, where V is an extension-closed pseudovariety of
groups. Then the completion of H with respect to the restriction
to H of the pro-V metric of G is a free pro-V group.
171 / 332
We consider the special case of the extension-closed
pseudovariety Gp for a prime integer p, for which the
denseness test can be done eﬃciently.
The next result may now be deduced from Proposition 14.2
and Proposition 14.3.
For group words w1, . . . , wm on n letters x1, . . . , xn, let
M(w1, . . . , wm) be the (integer) matrix whose (i, j)-entry is
the exponent of the reduced word in xj which is obtained from
wi by replacing by 1 all xk with k = j.
In particular, when m = n, M(w1, . . . , wn) is the matrix of the
continuous endomorphism of ΩnM which is determined by the
implicit operator deﬁned by the group terms w1, . . . , wn.
172 / 332
Proposition 15.6
Let G be a free group on n free generators and let
H = w1, . . . , wn be an n-generated subgroup of G. Then H is
dense in G if and only if M(w1, . . . , wn) is invertible mod p.
Proof.
By Baumslag’s Theorem asserting that the free group is residually
in Gp, we may regard G as the subgroup of ΩnGp generated by
{x1, . . . , xn}. Since the pro-Gp metric of G is the induced metric
from the metric of ΩnGp by Proposition 12.1, H is dense in G if
and only if it is dense in ΩnGp.
On the other hand, by Proposition 14.2, if H = w1, . . . , wn , then
H is dense in ΩnGp if and only if the associated implicit operator
(w1, . . . , wn) is Gp-invertible. By Proposition 14.3, the latter
condition is equivalent to the integer matrix M(w1, . . . , wn) being
invertible mod p.
173 / 332
Finally, the next result improves the general-purpose algorithm
in the proof of Theorem 15.3 by providing the means to
compute eﬃciently a proper clopen subgroup containing a
given non-dense ﬁnitely generated subgroup.
Proposition 15.7
Let H be a ﬁnitely generated subgroup of the free group G on n
free generators x1, . . . , xn and let {w1, . . . , wm} be generating
subset of H. Let A = (Z/pZ)n and consider the homomorphism
ϕ : G → A which sends xi to (0, . . . , 0, 1, 0, . . . , 0), where 1 is in
the ith position.
1. The subgroup H is dense in the pro-Gp metric of G if and
only if, mod p, the matrix M(w1, . . . , wm) has rank n.
2. If, mod p, the submatrix M(wr1 , . . . , wrn ) has rank n, then the
subgroup wr1 , . . . , wrn is dense.
3. If, mod p, the matrix M(w1, . . . , wm) has rank less than n,
then ϕ−1ϕ(H) is a proper clopen subgroup of G containing H.
174 / 332
Proof.
Since Z/pZ is a ﬁeld, a square matrix with entries in it is invertible
if and only if the matrix has rank n. Moreover, an m × n matrix
has rank n if and only if it contains n rows whose corresponding
submatrix has rank n. On the other hand, since ϕ(H) is generated
by the rows of the matrix M(w1, . . . , wm), with the entries viewed
in Z/pZ, if, mod p, this matrix has rank less than n, then ϕ(H) is
a proper subgroup of the group A ∈ Gp. This proves (3) and shows
that H is not dense in G. The statements (1) and (2) now follow
using Proposition 15.6.
Thus, for the pro-Gp metric of a ﬁnitely generated free group
G, combining part (3) of Proposition 15.7 and
Proposition 15.1, one may compute a proper clopen subgroup
containing a given ﬁnitely generated subgroup H which is not
dense in G.
175 / 332
To illustrate the above algorithms, we present an example in detail. For this purpose,
we consider again the subgroup H of the free group G on the free generators a, b, c of
Example 1: H is generated by the group words ab−1c−1a, a−1b−1ac−1a, bc−1a. The
corresponding integer matrix is
M0 =


2 −1 −1
1 −1 −1
1 1 −1


and has determinant 2. Hence H is dense in G with respect to the pro-Gp metric for
every odd prime p. For the pro-G2 metric of G, the rank of the matrix M0 mod 2 is 2.
More precisely, if ϕ0 : G → (Z/2Z)3 is the appropriate mapping given by
Proposition 15.7, then H ⊆ ϕ−1
0 ϕ0(H) G. The clopen subgroup ϕ−1
0 ϕ0(H) may be
computed as the fundamental group of the automaton which represents the action of
a, b, c on the right of the right cosets of ϕ0(H), which is represented in Figure 3.
ϕ0(H) ϕ0(H)(0, 1, 0)
b, c
b, c
a a
Figure: The automaton of K1
The clopen subgroup K1 in question is therefore freely generated by
{a, bab−1, b2, bc, cb−1}. The free factor L1 is obtained by taking the fundamental
group of the image of A(H) in A(K1). Recall the automaton A(H) as given in
Figure 177.
176 / 332
1
2
3
45
ab
a
b
a c
b
Figure: The automaton A(H)
The states 1, 2, 4 are mapped to ϕ(H) while 3, 5 are mapped to ϕ(H)(0, 1, 0) and the
only missing edge from the automaton of A(K1) is the edge c from the state
ϕ(H)(0, 1, 0) to ϕ(H), which corresponds to the generator bc of K1. Hence L1 is the
subgroup generated by {a, bab−1, b2, cb−1}. Let b1 = bab−1, b2 = b2 and
c1 = cb−1. Then the elements of H may be expressed as follows:
ab−1
c−1
a = ab−1
2 c−1
1 a
a−1
b−1
ac−1
a = a−1
b−1
2 b1
bc−1
a = c−1
1 a
which are now viewed as generating a subgroup H1 of the free group G1 on the set
a, b1, b2, c1. The matrix corresponding to the generators of H1 is
M1 =


2 0 −1 −1
−1 1 −1 0
1 0 0 −1


which, mod 2, has rank 3. Hence H is not dense in L1 and we need to compute a
clopen subgroup K2 of L1 and a free factor L2 of K2 containing H. 177 / 332
Since the rank of M1 mod 2 is 3, the image of H1 under the homomorphism
ϕ1 : G1 → (Z/2Z)4 has index 2 and again we obtain a 2-state permutation automaton
for K2, which is represented in Figure 5.
ϕ1(H1) ϕ1(H1a)
a, b2, c1
a, b2, c1
b1 b1
Figure: The automaton of K2
To obtain the image of A(H1) in this automaton, it suﬃces to read through each of
the generators of H1, starting from the initial state, and keeping only the states and
edges which are used. Figure 6 represents the subautomaton which is thus obtained,
whose fundamental group is the required free factor L2 of K2.
178 / 332
ϕ1(H1) ϕ1(H1a)
a, b2
a, c1
b1
Figure: The automaton of L2
Choosing the edge labeled b2 for the generating tree, we obtain the following free
generators for L2:
b1, a1 = ab−1
2 , a2 = b2a, c2 = b2c1. (3)
In terms of these generators, the expressions for the generators of H1 are the following:
ab−1
2 c−1
1 a = a1c−1
2 a2
a−1
b−1
2 b1 = a−1
2 b1
c−1
1 a = c−1
2 a2
The matrix of these generators with respect to the generators of L2 in the order given
by (3) is
M2 =


0 1 1 −1
1 0 −1 0
0 0 1 −1


which again has rank 3.
179 / 332
Proceeding as above, we get a canonical homomorphism ϕ2 : G2 → (Z/2Z)4, where
G2 is the free group on the generators b1, a1, a2, c2. Let H2 be the subgroup of G2
generated by a1c−1
2 a2, a−1
2 b1, c−1
2 a2. The new clopen subgroup K3 is the fundamental
group of the automaton in Figure 7.
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
b1, a2, c2
a1 a1
Figure: The automaton of K3
Figure 8 gives the subautomaton which is obtained by reading through the preceding
automaton the generators of H2.
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
a1
Figure: The automaton of L3
Choosing the edge labeled c2 for the generating tree, we obtain the following free
generators for L3:
a1, a3 = c−1
2 a2, b3 = c−1
2 b1. (4)
180 / 332
ϕ2(H2) ϕ2(H2b1)
b1, a2, c2
a1
a1, a3 = c−1
2 a2, b3 = c−1
2 b1.
The corresponding expressions for the generators of H2 are:
a1c−1
2 a2 = a1a3
a−1
2 b1 = a−1
3 b3
c−1
2 a2 = a3
whose matrix has rank 3 mod 2, 3 being also the rank of L3. Hence H2 is dense in L3
and the closure of H = ab−1c−1a, a−1b−1ac−1a, bc−1a in G is obtained by
substituting back in terms of a, b, c the expressions for the generators of L3 given
in (4):
a1 = a1 = ab−1
2 = ab−2
a3 = c−1
2 a2 = c−1
1 b−1
2 b2a = bc−1
a
b3 = c−1
2 b1 = c−1
1 b−1
2 b1 = bc−1
b−2
bab−1
= bc−1
b−1
ab−1
Since the generators of L3 are all recognized by A(H), we conclude that H is closed in
the pro-G2 metric of G.
181 / 332
In terms of generators, we obtained the following chain of subgroups approximating
the closure of H, where we also indicate on the right the corresponding congruences
on A(H) as given by the partitions of the state set:
G = a, b, c
∪
K1 = a, bab
−1
, b
2
, bc, cb
−1
∪
L1 = a, bab
−1
, b
2
, cb
−1
{1, 2, 4|3, 5}
∪
K2 bab
−1
, ab
−2
, b
2
a, b
2
cb
−1
, cb
−3
, b
3
ab
−3
, b
4
∪
L2 bab
−1
, ab
−2
, b
2
a, b
2
cb
−1
{1|2, 4|3, 5}
∪
K3 ab
−2
, bc
−1
a, bc
−1
b
−1
ab
−1
, b
2
ab
2
cb
−1
, babcb
−1
, b
2
cbcb
−1
, bc
−1
b
−2
acb
−1
∪
L3 ab
−2
, bc
−1
a, bc
−1
b
−1
ab
−1
{1|2|3|4|5}
H = ab
−1
c
−1
a, a
−1
b
−1
ac
−1
a, bc
−1
a
Exercise 15.8
Verify that the above calculations are correct.
182 / 332
The above calculations also show that H is not Gp-extendible for every odd prime p
while it is G2-extendible. An G2-extension of the automaton A(H) may be recovered
from our calculations. It is the permutation automaton associated with the following
clopen subgroup:
K = ab−2
, bc−1
a, bc−1
b−1
ab−1
,
b2
ab2
cb−1
, babcb−1
, b2
cbcb−1
, bc−1
b−2
acb−1
,
cb−3
, b3
ab−3
, b4
,
b2
a · cb−3
· (b2
a)−1
, b2
a · b3
ab−3
· (b2
a)−1
, b2
a · b4
· (b2
a)−1
,
bc, a · bc · a−1
,
b2
a · bc · (b2
a)−1
, b2
a · abca−1
· (b2
a)−1
.
Exercise 15.9
Explain in general how to compute a V-extension of a V-extendible ﬁnite inverse
reduced automaton, assuming the appropriate hypotheses on the extension-closed
pseudovariety of groups V.
183 / 332
One may calculate the following picture for A(K) and that the transition
monoid of this automaton is a group of order 128. Since it would be too
tedious to do it by hand, this calculation was carried out using some adequate
Mathematica routines for the symbolic computations and the package graphviz
for the drawing itself, which was then converted by hand to GasTeX for
readability. The numbering of states was chosen to facilitate the identiﬁcation
of the subautomaton A(H). New edges and states are in red.
6
7
5
8
4
2
3
1
a
b
c
b
c
b
a
c
b
c
a
c
a
b
c
b
c
c
b
b
a
a
a
a
Figure: A G2-extension of A(H)
184 / 332
Exercise 15.10
Show that the above algorithms for the pseudovariety Gp (to test
denseness, to compute the closure, to exhibit a Gp-extension, if
one exists) require only polynomial time in the input, which may
be either a ﬁnite list of group words over a ﬁnite alphabet A, or the
reduced inverse automaton of the subgroup of the free group on A
that they generate. More precisely, estimate the time complexity of
the algorithms.
185 / 332
Outline
σ-fullness
σ-reducibility of the V-separation problem
pro-V-metrics
Inverse automata
V-invertibility of endomorphisms
Computing closures of finitely generated
subgroups
The Pin-Reutenauer procedure
186 / 332
The Pin-Reutenauer procedure
Let us consider again the problem studied by Pin and
Reutenauer [PR91]: given a regular language L ⊆ A+ and a
word w ∈ A+, decide whether w can be separated from L by a
G-recognizable language.
Since G is κ-reducible for the separation problem, the problem
is equivalent to deciding whether w ∈ clκ,G(L).
So, the idea is to compute the subset clκ,G(L) of the free
group Ωκ
AG.
Since L is regular, we may assume that it is given by some
regular expression.
As every ﬁnite subset of Ωκ
AG fullfullis closed and closure
behaves well with respect to union, the key question is how
the closure operator clκ,G( ) behaves well with respect to the
multiplication of subsets and the Kleene star operation.
187 / 332
In general, for an arbitrary pseudovariety V and implicit
signature σ, we have the inclusion
clσ,V(K L) ⊇ clσ,V(K) clσ,V(L), (5)
simply because the multiplication in Ωκ
AV is continuous.
Note: in a compact semigroup, the equality K L = K L holds.
For a subset X of a σ-algebra S, denote by S σ the
σ-subalgebra generated by X.
The analogue of (5) for Kleene star is the inclusion
clσ,V(L+
) ⊇ clσ,V(L) σ (6)
The proof of (6) is a bit more delicate and depends on the
following lemma.
188 / 332
Lemma 16.1
Let V be a pseudovariety of semigroups and let S be a pro-V
semigroup. Then the following evaluation mapping is continuous
for every positive integer n:
ΩnV × Sn
→ S
(w, s1, . . . , sn) → wS (s1, . . . , sn).
Proof.
Since V-implicit operations commute with continuous homomorphisms
between pro-V semigroups, in view of Proposition 5.1 it suﬃces to
consider the case where S ∈ V.
Note that ΩnV(S) is ﬁnite, say again by Proposition 5.1. Moreover,
when ΩnV and S are both ﬁnite, the continuity of the evaluation
mapping is trivial.
Since, in terms of implicit operations, the natural projection
ΩnV → ΩnV(S) is given by restriction, we deduce the general case.
189 / 332
The inclusion clσ,V(L) σ ⊆ clσ,V(L+
) follows from the next
proposition.
Proposition 16.2
Let V be a pseudovariety, σ and implicit signature, and L a subset
of Ωσ
AV. Then clσ,V(L+
) is a σ-subalgebra of Ωσ
AV.
Proof.
Let u ∈ ΩmS be an implicit operation from σ, and let v1, . . . , vm be
elements of clσ,V(L+
). There are sequences with the following properties:
a sequence (un)n, of words from {x1, . . . , xm}+
, converging
to u;
for each i ∈ {1, . . . , m}, a sequence (vi,n)n, of elements of L+
,
converging to vi .
For each n, the element (un)ΩAV(v1,n, . . . , vm,n) is a product of elements
from L+
and, therefore, also belongs to L+
. By Lemma 16.1, we have
lim(un)ΩAV(v1,n, . . . , vm,n) = uΩAV(v1, . . . , vm).
Hence uΩAV(v1, . . . , vm) belongs to clσ,V(L+
).
190 / 332
Theorem 16.3 (Pin and Reutenauer [PR91])
For the pseudovariety V = G, the signature σ = κ, and a regular
language L ⊆ A+, equality holds in both formulas (5) and (6).
Some comments on the proof:
The proof establishes a stronger result than (6), namely that
clκ,G(L+
) = L κ.
The main reason for not needing to use clκ,G(L) instead of L on the
right hand side is M. Hall’s Theorem 13.5.
The proof depends on several ingredients from language theory,
such as a theorem of Anissimov and Seifert, stating that the
rational7
subgroups of Ωκ
AG are the ﬁnitely generated subgroups,
and a theorem of Fliess, stating that the rational subsets of Ωκ
AG
form a Boolean algebra. (See [Ber79, Section III.2] —
http://www-igm.univ-mlv.fr/∼berstel/LivreTransductions/LivreTransductions.html.)
7
A subset of a monoid M is said to be rational if it can be obtained from the
empty set and the singleton subsets of M by using the operations of subset
multiplication and taking the submonoid X∗
generated by a subset X.
191 / 332
The theorem was initially deduced from a conjectured property of
free groups: that the product of ﬁnitely many ﬁnitely generated
subgroups of Ωκ
AG is closed in the pro-G metric.
This property follows from Ash’s Theorem on inevitable graphs
[Ash91] and was proved independently by Ribes and
Zalesski˘ı [RZ93], using proﬁnite group theory.
The theorem was found as an approach to a conjecture of J. Rhodes
(known as the Rhodes Type II Conjecture), which it implies. Ash’s
Theorem on inevitable graphs was also proved to establish Rhodes’
conjecture. (See [HMPR91] for the original statement and the
history of this conjecture.)
The Rhodes Type II Conjecture, now theorem, may be stated as
follows [AS00a].
Theorem 16.4 (Rhodes Type II)
Let S be a ﬁnite semigroup and let A be a generating subset. Consider
the κ-subsemigroup T of S × Ωκ
AG generated by the pairs (a, a) (a ∈ A).
Then, for an element s ∈ S, (s, 1) ∈ T if and only if, for every ﬁnite
group G, and every subsemigroup U of S × G, which projects onto the
ﬁrst component, (s, 1) ∈ U. 192 / 332
Other pseudovarieties for which the
Pin-Reutenauer procedure holds
We say that the Pin-Reutenauer procedure holds for a
pseudovariety V and an implicit signature σ if the following
equalities hold for all subsets L of Ωσ
AV:
clσ,V(K L) = clσ,V(K) clσ,V(L) (7)
clσ,V(L+
) = clσ,V(L) σ. (8)
Note that if the pseudovariety V contains N, then there is
always an implicit signature for which the Pin-Reutenauer
procedure holds (cf. Proposition 7.3), for example the trivial
signature { · }. But, this in general too small for the
pseudovariety to be full with respect to it.
193 / 332
In a sense at the other extreme, if we take σ to consist of all
(ﬁnitary) implicit operations, then Ωσ
AV = ΩAV and
clσ,V(L) = L is the closure of L in ΩAV. So, the equality (7)
certainly holds in this case, by compactness of ΩAV. On the
other hand, clσ,V(L+) is the closure of a subsemigroup,
whence a closed subsemigroup of ΩAV, namely the closed
subsemigroup generated by L, which is therefore contained
in clσ,V(L) σ. The reverse inclusion is given by
Proposition 16.2.
Hence, for every pseudovariety V, there is some implicit
signature for which the Pin-Reutenauer procedure holds and V
is σ-full. The question is whether it holds for small such
signatures, such as κ.
The other key question is under what conditions one can turn
the Pin-Reutenauer procedure into an algorithm to test
membership of a given word w ∈ L in the closure clσ,V(L) of a
given regular language L ⊆ A+.
194 / 332
Here are some recent results.
Theorem 16.5 (JA-JCCosta-MZeitoun)
Suppose that V and W are σ-full pseudovarieties of semigroups
such that V ⊆ W. If the Pin-Reutenauer procedure holds for W
then it also holds for V.
Theorem 16.6 (JA-JCCosta-MZeitoun)
The Pin-Reutenauer procedure holds for A in the signature κ.
As was already mentioned, the same authors proved that A
and R are κ-full. Hence the preceding two theorems yield the
following result.
Corollary 16.7
The Pin-Reutenauer procedure holds for R in the signature κ.
195 / 332
Part III
Relatively free proﬁnite semigroups
and Symbolic Dynamics
196 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
197 / 332
Semigroups of implicit operators
Let wi ∈ ΩnS be an n-ary implicit operation for each
i ∈ {1, . . . , n}.
Given a proﬁnite semigroup S, the n-tuple induces a
continuous mapping
[w1, . . . , wn]S : Sn
→ Sn
(s1, . . . , sn) → (w1)S (s1, . . . , sn), . . . , (wn)S (s1, . . . , sn) .
The composition of two such transformations of Sn is again a
transformation of the same form, and thus they constitute a
semigroup, which we call the semigroup of n-ary implicit
operators of S and denote On(S).
In particular, we may iterate an implicit operator
f = [w1, . . . , wn]S by considering its successive powers
f , f 2, f 3, . . ..
198 / 332
The following result is immediate from the commutation of
implicit operations with comtinuous homomorphisms between
proﬁnite semigroups.
Lemma 17.1
Let w1, . . . , wn ∈ ΩnS be n-ary implicit operations and let
ϕ : S → T be a continuous homomorphism between proﬁnite
semigroups. Then the following diagram commutes:
Sn [w1,...,wn]S
GG
ϕn

Sn
ϕn

Tn [w1,...,wn]T
GG Tn.
199 / 332
Lemma 17.2
Let S be a proﬁnite semigroup and let f ∈ On(S) be an n-ary
implicit operator on S. Then, for every (s1, . . . , sn) ∈ Sn, the
sequence f k!(s1, . . . , sn) k
of elements of Sn converges. In other
words, the sequence (f k!)k of transformations of Sn converges
pointwise. Moreover, the limit is an idempotent transformation
of Sn.
200 / 332
Proof.
By deﬁnition of proﬁnite semigroup, S admits a complete metric d.
We may endow the product space Sn with various metrics, among
which the maximum metric d deﬁned by
d (s1, . . . , sn), (t1, . . . , tn) = max{d(si , ti ) : i = 1, . . . , n}.
This deﬁnes a complete metric structure on Sn. Thus, to prove
that the sequence f k!(s1, . . . , sn) k
converges, it suﬃces to show
that it is a Cauchy sequence.
By Proposition 5.1 and Lemma 17.1, it suﬃces to consider the
case where S is a ﬁnite semigroup, in which case the result
amounts to the convergence of the corresponding sequence f k! in
the ﬁnite monoid of transformations of Sn, where indeed we have
observed that it converges to an idempotent.
201 / 332
We denote the limit lim[w1, . . . , wn]k!
S by [w1, . . . , wn]ω
S .
In particular, given w1, . . . , wn ∈ ΩnS, we may consider the
following n-tuple of n-ary implicit operations:
(v1, . . . , vn) = [w1, . . . , wn]ω
ΩnS
(x1, . . . , xn).
Lemma 17.3
With the above notation, if S is a proﬁnite semigroup, then
[v1, . . . , vn]S = [w1, . . . , wn]ω
S .
Thus, the transformation [w1, . . . , wn]ω
S is again an implicit
operator and the semigroup On(S) is closed under taking ω-powers.
202 / 332
Proof.
Let (s1, . . . , sn) be an n-tuple of elements of S. Then there is a
unique continuous homomorphism ϕ : ΩnS → S such that
ϕ(xi ) = si (i = 1, . . . , n).
In view of Lemma 17.1 and taking into account that ϕn is
continuous, we obtain
[v1, . . . , vn]S (s1, . . . , sn)
= ϕn
[v1, . . . , vn]ΩnS(x1, . . . , xn)
= ϕn
lim[w1, . . . , wn]k!
ΩnS
(x1, . . . , xn)
= lim ϕn
[w1, . . . , wn]k!
ΩnS
(x1, . . . , xn)
= lim[w1, . . . , wn]k!
S (s1, . . . , sn)
= [w1, . . . , wn]ω
S (s1, . . . , sn),
which establishes the desired equality.
203 / 332
Since ΩnS is a proﬁnite semigroup freely generated by the set
{x1, . . . , xn}, the n-tuples of n-ary implicit operations
(w1, . . . , wn) are in bijection with the continuous
endomorphisms ϕ(w1,...,wn) of ΩnS, where ϕ(w1,...,wn)(xi ) = wi
(i = 1, . . . , n).
On the other hand, they are also in bijection with n-ary
implicit operators on ΩnS, namely through the formula
(w1, . . . , wn) = [w1, . . . , wn]ΩAS(x1, . . . , xn).
For a proﬁnite semigroup S, denote by End S the monoid of
continuous endomorphisms of S, acting on the left.
204 / 332
Proposition 17.4
The following mapping is an anti-isomorphism of semigroups:
Θ : End ΩnS → On(ΩnS)
ϕ → [ϕ(x1), . . . , ϕ(xn)]ΩnS.
Proof.
We have already observed that the above mapping is a bijection, and described
its inverse. So, it remains to verify that it is an anti-homomorphism of
semigroups.
Let ϕ, ψ ∈ End ΩnS and let wi = ψ(xi ) (i = 1, . . . , n). Taking into account
Lemma 17.1, we obtain
Θ(ϕ ◦ ψ) = [ϕ(ψ(x1)), . . . , ϕ(ψ(xn))]ΩnS
= [ϕ(w1), . . . , ϕ(wn))]ΩnS
= [w1(ϕ(x1), . . . ϕ(xn)), . . . , wn(ϕ(x1), . . . ϕ(xn))]ΩnS
= [w1, . . . , wn]ΩnS ◦ [ϕ(x1), . . . ϕ(xn)]ΩnS
= Θ(ψ) ◦ Θ(ϕ).
205 / 332
Lemma 17.5
Let ϕk, ϕ ∈ End ΩnS (k ≥ 0). Then (ϕk)k convergences pointwise
to ϕ if and only if (Θ(ϕk))k converges pointwise to Θ(ϕ).
Proof.
Let vk,i = ϕk(xi ) and vi = ϕ(xi ) (i = 1, . . . , n; k ≥ 0).
(⇒) For w1, . . . , wn ∈ ΩnS, we have
Θ(ϕk)(w1, . . . , wn)
= [vk,1, . . . , vk,n]ΩnS(w1, . . . , wn)
= (vk,1)ΩnS(w1, . . . , wn), . . . , (vk,n)ΩnS(w1, . . . , wn)
→ (v1)ΩnS(w1, . . . , wn), . . . , (vn)ΩnS(w1, . . . , wn)
= [v1, . . . , vn]ΩnS(w1, . . . , wn)
= Θ(ϕ)(w1, . . . , wn),
where the convergence step follows from Lemma 16.1.
206 / 332
(. . . )
(⇐) Let w ∈ ΩnS. Then we have
ϕk(w) = ϕk wΩnS(x1, . . . , xn)
= wΩnS vk,1, . . . , vk,n
= wΩnS [vk,1, . . . , vk,n]ΩnS(x1, . . . , xn)
→ wΩnS [v1, . . . , vn]ΩnS(x1, . . . , xn)
= ϕ wΩnS(x1, . . . , xn)
= ϕ(w),
where we use again Lemma 16.1 for the convergence step.
207 / 332
Corollary 17.6
For a continuous endomorphism ϕ of ΩnS, the sequence (ϕk!)
converges pointwise to an idempotent continuous endomorphism
of ΩnS.
The idempotent in question is denoted ϕω and is called the
ω-power or ω-iterate of ϕ.
More generally, Hunter [Hun83] has shown that the monoid
End S of continuous endomorphisms of a ﬁnitely generated
proﬁnite semigroup S is proﬁnite. Since it is usually not
ﬁnitely generated, this result does not ﬁt in the realm of our
metric approach to proﬁnite semigroups. For those that know
about topology of function spaces, the topology used in End S
is the topology of pointwise convergence (i.e., as a subspace
of the product space SS ), and turns out to coincinde with the
compact-open topology (i.e., the topology of uniform
convergence). See also [Alm02, AV06a, Alm05b, Ste11].
208 / 332
Examples
The ω-iteration of continuous endomorphisms of ΩnS, or of
implicit operators on ΩnS can be used to construct useful
implicit operations.
Let ϕ ∈ End Ω1S be deﬁned by ϕ(x1) = xp
1 . Then
ϕk(x1) = xpk
1 and ϕω(x1) = xpω
1 . Recall that we used the
implicit operation xpω
1 previously to deﬁne the pseudovariety
Gp in terms of pseudoidentities: Gp = [[xpω
1 = 1]].
209 / 332
Given elements u and v of a proﬁnite semigroup S, let
[u, v] = uω−1
vω−1
uv,
an extension of the group commutator. Note, however, that,
if S is not a group, [u, v] idempotent may not be equivalent
to uv = vu.
Let ϕ ∈ End Ω2S be deﬁned by ϕ(x1) = [x1, x2] and
ϕ(x2) = x2. Note that ϕk(x1) is the iterated commutator
deﬁned recursively by [x1,1 x2] = [x1, x2] together with
[x1,k+1 x2] = [[x1,k x2], x2].
We let [x1,ω x2] = ϕω(x1), which is an implicit operation
in Ω2S.
Using a theorem of Zorn [Zor36], that states that a ﬁnite
group is nilpotent (i.e., a direct product of groups of prime
power order) if and only if it satisﬁes some identity of the
form [x,n y] = 1, it is now easy to solve Exercise 6.5(2):
Gnil = [[[x,ω y] = 1]].
210 / 332
The Prouhet-Thue-Morse substitution
When ϕ ∈ ΩAS extends an endomorphism of A+ it is also
called a (ﬁnite) substitution since applying ϕ to a word
corresponds to substituting each letter a ∈ A by the word
ϕ(a).
The substitution over the alphabet {a, b} deﬁned by
τ(a) = ab and τ(b) = ba was ﬁrst considered by
Prouhet [Pro51], and rediscovered by Thue [Thu06, Thu12]
and Hedlund and Morse [HM38].
Here is an example of a result involving it:
Theorem 17.7 (ˇSirˇsov [ˇS63])
The pseudovariety [[τω(a) = τω(b), xω = 1]] consists of all ﬁnite
groups admitting a normal nilpotent subgroup whose
corresponding factor group is a 2-group.
211 / 332
The substitution τ determines a binary implicit operator
[ab, ba]S on every proﬁnite semigroup S. How does it behave
on a ﬁnite group?
When iterating a transformation on a ﬁnite set, in a ﬁnite
number steps one must enter into a periodic orbit.
One possible way to visualize the action of our
Prouhet-Thue-Morse implicit operator on a ﬁnite group G is
to draw a square in which the sides stand for G, and a pixel,
an elementary square, for an element of G × G. One may
color each pixel so as to encode for instance how many
applications of the operator it takes to reach a periodic orbit,
and to distinguish between the diﬀerent periodic orbits.
It is somewhat striking that one obtains pictures like those in
the following two pages. The ordering of the elements in the
groups is that given by GAP [GAP06], a computer algebra
system that was used to carry out the calculations. The
groups are Z/858Z and V4 A3.
212 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
213 / 332
Finite factor complexity
Given w ∈ ΩAS, denote by F(w) the set of words u ∈ A+
which are factors of w, and let Fn(w) = F(w) ∩ An.
The complexity sequence qw (n) is deﬁned by letting
qw (n) = |Fn(w)|, where n is a positive integer.
Lemma 18.1
Let w ∈ ΩAS \ A+ and let u ∈ F(w). If there is no a ∈ A such
that ua ∈ F(w), then there is factorization of the form w = vu.
214 / 332
Proof.
Let (wn)n be a sequence of ﬁnite words converging to w. For each
z ∈ A+, the set Cz = (ΩAS)1z(ΩAS)1 = A∗zA∗ is a clopen set
such that Cz ∩ A+ = A∗zA∗. By hypothesis, w belongs to Cu and
so we may assume that so do all wn, since Cu is open. On the other
hand, since Cua is closed, we may assume that no wn ∈ Cua, for
any a ∈ A. This leaves only one place for u to be a factor of each
wn, namely as a suﬃx: wn = vnu for some vn ∈ A∗. Since ΩAS is
compact, some subsequence of (vn)n converges to some v ∈ ΩAS.
By continuity of multiplication, it follows that w = vu.
215 / 332
Lemma 18.2
Let w ∈ ΩAS. Then the following formula holds for every positive
integer n:
qw (n + 1) − qw (n) =
u∈Fn(w)
(|{a ∈ A : ua ∈ Fn+1(w)}| − 1). (9)
Proof.
Each factor of w of length n + 1 is of the form ua, for some a ∈ A,
which yields the following formula:
qw (n + 1) =
u∈Fn(w)
|{a ∈ A : ua ∈ Fn+1(w)}|.
Subtracting qw (n) = u∈Fn(w) 1, we obtain formula (9).
216 / 332
Because of the suﬃx of length n appearing nowhere else in w
(cf. Lemma 18.1), there may be one negative term in the
sum (9). However, the sum is always nonnegative for
w ∈ ΩAS \ A+.
Lemma 18.3
Let w ∈ ΩAS \ A+. Then the sequence qw (n) is increasing.
217 / 332
Proof.
Suppose that qw (n + 1) < qw (n). Then, as argued above, the suﬃx u of
length n of w must not appear elsewhere in w as a factor, and all other
terms in the sum must be zero: for every v ∈ Fn(w) \ {u}, there is
exactly one letter av ∈ A such that vav ∈ Fn+1(w).
Now, suppose that tz is a ﬁnite suﬃx of w, with |t| = n. Then there is
no word z with |z | > |z| such that tz is a suﬃx of w. For, otherwise,
we may take a counterexample (t, z) with |z| minimum. Then z = 1 for,
else, we must have t = u and we know that u does not appear elsewhere
in w. Hence, z = atz1 and, if we write t = bt1, with b ∈ A, then (t1, z1)
is still a counterexample and |z1| < |z|, which contradicts our choice of
counterexample.
Hence every factor of length n of w which appears as part of a ﬁnite
suﬃx, can be found as such in only one position. Since Fn(w) ⊆ An
is
ﬁnite, we conclude that w cannot have arbitrarily long ﬁnite suﬃxes,
whence w ∈ A+
, contrary to the hypothesis.
218 / 332
We say that a ﬁnite word u is primitive if it is not of the form
vn for some integer n > 1.
Theorem 18.4 ([AV06a])
Suppose that w ∈ ΩAS \ A+ is such that qw (n) ≤ n for some n.
Then there exist ﬁnite words x, y, and z and an inﬁnite ν ∈ ˆZ+
such that w = xyνz, |xy| ≤ n, and |yz| ≤ n.
Corollary 18.5 ([AV06a])
Let w be any pseudoword which is not of the form xyνz for some
ﬁnite words x, y, z and some ν ∈ ˆZ+. Then qw (n) ≥ n + 1 for
every n.
219 / 332
The next result identiﬁes maximal subgroups of ΩAS of small
complexity.
Theorem 18.6 ([AV06a])
Suppose that w lies in a subgroup of ΩAS and qw (n) ≤ n for
some n. Then the H-class of w is a free procyclic group with
generator of the form yω+1 for some word y of length at most n.
In particular, for each positive n, there are only ﬁnitely many
H-classes of such pseudowords w.
Note that J -equivalent elements of ΩAS have the same
complexity.
Corollary 18.7
The complexity of any non-procyclic subgroup of ΩAS is at least
q(n) ≥ n + 1.
220 / 332
Sturmian pseudowords
Thus, the minimum possible complexity for a non-procyclic
subgroup of ΩAS is q(n) = n + 1.
Then q(1) = 2, which means that there are exactly two letters
involved in the subgroup in question.
We say that w ∈ ΩAS is Sturmian if qw (n) = n + 1 for every
n ≥ 1.
221 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
222 / 332
Primitive substitutions
Since substitutions over a one-letter alphabet are not very
interesting, we assume from hereon that |A| ≥ 2.
A ﬁnite substitution ϕ ∈ End ΩAS is said to be primitive if
there is some positive integer N such that, for every two
letters a, b ∈ A, a appears in the word ϕN(b).
Proposition 19.1
Let ϕ ∈ End ΩAS be a primitive ﬁnite substitution. Then all
pseudowords of the form ϕω(a), with a ∈ A, lie in the same
J -class.
Proof.
Let N be as above and let a, b ∈ A. Then a is a factor of ϕkN(b)
for every k. By compactness, it follows that a is also a factor
of ϕω(b) = (ϕN)ω(b), say ϕω(b) = uav. Since ϕω is idempotent,
we deduce that ϕω(b) = ϕω(u) · ϕω(a) · ϕω(v), which shows that
ϕω(a) is a factor of ϕω(b).
223 / 332
We have already seen one classical example of primitive ﬁnite
substitution, namely the Prouhet-Thue-Morse substitution
a → ab, b → ba.
Another classical example is that of the so-called Fibonacci
substitution ϕ(a) = ab, ϕ(b) = a. Note that the fn = |ϕn(b)|
satisﬁes the recurrence relation fn+2 = fn+1 + fn, with
f1 = f2 = 1.
ϕω(b) is an example of Sturmian pseudoword.
More generally, the following is a consequence of a theorem of
Mignosi and S´e´ebold [MS93] on inﬁnite words.
Theorem 19.2
Let ϕ ∈ End Ω2S be a primitive substitution. Then ϕω(x1) is
Sturmian if and only if ϕ induces an automorphism of the free
group Ωκ
2G.
224 / 332
By Proposition 19.1, one may consider the complexity of a
primitive ﬁnite substitution ϕ ∈ End ΩAS.
Theorem 19.3 ([ELR75, Pan84])
The complexity of a primitive ﬁnite substitution is at most linear.
225 / 332
Proof.
Let ϕ ∈ End ΩAS be a primitive ﬁnite substitution, let q be its complexity, and
let n be a positive integer. There is some p such that
min
a∈A
|ϕp−1
(a)| ≤ n ≤ min
a∈A
|ϕp
(a)|. (10)
Then, every word in Fn(ϕω
(a)) must be a factor of some ϕp
(a) or of some
ϕp
(ab), with ab a factor of ϕω
(ab). For each such two-letter word ab, there are
at most |ϕp
(ab)| factors of length n. Hence, if we let r = |A|2
, then we have
q(n) ≤ 2r max
a∈A
|ϕp
(a)|. (11)
By the Perron-Frobenius Theorem (19.4), there are constants α, c, d > 0 such
that
cαp
≤ min
a∈A
|ϕp
(a)| ≤ max
a∈A
|ϕp
(a)| ≤ dαp
. (12)
Combining the inequalities (11) and (12) and taking also into account (10), we
obtain
q(n) ≤ 2r dαp
≤ 2r
d
c
α n.
226 / 332
The Perron-Frobenius Theorem
Let ϕ ∈ End ΩAS be a ﬁnite substitution. For each a, b ∈ A,
one may consider the number |ϕ(a)|b of occurrences of the
letter b in the word ϕ(a). This deﬁnes a matrix M(ϕ) with
nonnegative integer entries.
Note that:
the sum of the entries in the row corresponding to a ∈ A is
|ϕ(a)|;
for another ﬁnite substitution ψ ∈ End ΩAS,
M(ϕ ◦ ψ) = M(ϕ)M(ψ);
thus M(ϕk
) = (M(ϕ))k
for every k ≥ 1;
hence ϕ is primitive if and only if tere exists k ≥ 1 such that
(M(ϕ))k
has all entries positive; a matrix with nonnegative
real entries satisfying this property is said to be primitive;
An n × n real matrix M is said to be irreducible if, for every
pair of indices i, j, there is a power Mk whose i, j-entry is
nonzero.
227 / 332
Theorem 19.4 (Perron-Frobenius)
Let M be a nonnegative irreducible matrix. Then there is a
positive simple eigenvalue α such that
α ≥ |λ| for every other eigenvalue λ and
α admits an eigenvector whose coordinates are all positive.
In case M is primitive, α > |λ| for every other eigenvalue λ.
The special, dominant eigenvalue α, is called the
Perron-Frobenius eigenvalue of the matrix M.
See http://en.wikipedia.org/wiki/Perron-Frobenius theorem
for the signiﬁcance of the theorem and several proofs.
228 / 332
For the proof of the existence of constants c, d such that the
inequalities (12) hold, let M be a r × r nonnegative primitive matrix
and let α be its Perron-Frobenius eigenvalue. Let v = (v1, . . . , vr )
be a corresponding positive eigenvector: Mv = αv, whence
Mp
v = αp
v for all p ≥ 1.
Let (Mp
)i,j denote the i, j entry of the matrix Mp
.
For i = 1, . . . , r, we have
r
j=1
(Mp
)i,j vj = αp
vi .
Hence, if c0 = mini vi and d0 = maxi vi , then we get
c0
r
j=1(Mp
)i,j ≤ d0αp
for every i, whence
max
i
r
j=1
(Mp
)i,j ≤
d0
c0
αp
.
On the other hand, we have c0αp
≤ d0
r
j=1(Mp
)i,j for every i,
which gives
c0
d0
αp
≤ min
i
r
j=1
(Mp
)i,j .
229 / 332
Examples
Consider the Prouhet-Thue-Morse substitution τ(a) = ab,
τ(b) = ba.
Then M(τ) =
1 1
1 1
has characteristic polynomial
(1 − x)2 − 1 = x(x − 2) and eigenvalues 0 < 2.
So, 2 is the Perron-Frobenius eigenvalue. The corresponding
eigenspace is generated by (1, 1).
For w = τω(a), the proof of Theorem 19.3 gives
qw (n) ≤ 2 × 22
×
1
1
× 2n = 16n.
It turns out that this is about double the exact value, which
has been computed (see [Fog02, Proposition 5.1.9]).
230 / 332
Let ϕ be the Fibonacci substitution: ϕ(a) = ab, ϕ(b) = a.
Then M(ϕ) =
1 1
1 0
has characteristic polynomial
(1 − x)(−x) − 1 = x2 − x − 1 and eigenvalues 1−
√
5
2 < 1+
√
5
2 .
The Perron-Frobenius eigenvalue, 1+
√
5
2 , has eigenspace
generated by the vector (1+
√
5
2 , 1).
For w = ϕω(a), the proof of Theorem 19.3 gives
qw (n) ≤ 2×22
×
1 +
√
5
2
2
×
1 +
√
5
2
n = 2(1+
√
5)3
n 68n,
while we know that qw (n) = n + 1.
231 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
232 / 332
Entropy
The complexity (function) of a pseudoword has the following
log-subadditive property:
Lemma 20.1
Let w ∈ ΩAS. Then the inequality qw (r + s) ≤ qw (r) qw (s) holds
for all positive integers r and s.
Proof.
A factor of w of length r + s is of the form uv, where u ∈ Fr (w)
and v ∈ Fs(w).
Lemma 20.2 (Fekete’s Lemma)
Let (tn)n be a sequence of real numbers such that tr+s ≤ tr + ts
for all r, s ≥ 1. Then we have lim tn
n = inf tn
n .
233 / 332
Proof.
Let = inf tn
n and let be a positive real number. Let K be an
index such that tK
K < + 2. There is also a positive integer M
such that tr
KM < 2 for r < K.
Let n ≥ KM and write n = qK + r with r < K. Then
≤
tn
n
≤
qtK
qK + r
+
tr
n
≤
qtK
qK
+
tr
KM
≤
tK
K
+
tr
KM
≤ +
2
+
2
which establishes the lemma.
234 / 332
Let A be a ﬁnite alphabet and m = |A|.
For a pseudoword w ∈ ΩAS \ A+, by Lemmas 20.1 and 20.2,
the following limit exists:
h(w) = lim
n→∞
1
n
logm qw (n).
It is called the entropy of w.
Since 1 ≤ qw (n) ≤ mn, the entropy h(w) is a real number in
the interval [0, 1].
If u, v ∈ ΩAS \ A+ are such that u is a factor of v, then
h(u) ≤ h(v).
235 / 332
Iteration of primitive ﬁnite substitutions leads to minimum
entropy:
Theorem 20.3
Let ϕ ∈ End ΩAS be a primitive ﬁnite substitution. Then we have
h(ϕω(a)) = 0.
Proof.
Let w = ϕω(a). By Theorem 19.3, there is some constant C such
that qw (n) ≤ Cn, for every n ≥ 1. Hence h(w) = 0.
A much more general result is uncovered below in
Theorem 20.8.
236 / 332
Proposition 20.4
Let w ∈ ΩAS \ A+. Then h(w) = 1 if and only if every u ∈ ΩAS is
a factor if w.
Proof.
Since h(w) = inf 1
n logm qw (n), we have h(w) = 1 if and only if
qw (n) = mn for every n, that is if and only if every ﬁnite word is a
factor of w. But every element of ΩAS is the limit of a sequence of
ﬁnite words. Hence every ﬁnite word is a factor of w if and only if
every pseudoword is a factor of w.
237 / 332
An ideal in a semigroup S is a nonempty subset I such that
SI ∪ IS ⊆ I.
A minimal ideal is an ideal which is not properly contained in
any other ideal.
Some semigroups, such as A+, have no minimal ideals.
Note that a semigroup cannot have more than one minimal
ideal: given two ideals I and J, IJ is an ideal contained in
both of them.
When there is one minimal ideal, we call it the minimum ideal,
since it is indeed contained in every ideal. The minimum ideal
of a semigroup is often also called its kernel and denoted
K(S).
For a semigroup S, the elements of the minimum ideal, if it
exists, are precisely those elements of S which admit every
element of S as a factor.
238 / 332
Proposition 20.5
Every compact metric semigroup has a minimum ideal.
Proof.
Let S be a compact metric semigroup. For each n, by compactness
S is covered by a ﬁnite number of open balls of radius 1
n . If we
choose such balls and collect their centers for varying n in a set, we
obtain a countable dense subset X.
Let X = {x1, x2, . . . , xn, . . .} be an enumeration of the elements
of X. Let s be any limit of a subsequence of the sequence
(x1 · · · xn)n. Then s admits every element of X as a factor and,
since X is dense in S, every element of S must be a factor of S.
Hence s ∈ K(S).
239 / 332
In particular, every ﬁnite and every proﬁnite semigroup has a
minimum ideal.
Proposition 20.4 means that w ∈ ΩAS has maximum entropy
(one) if and only if w ∈ K(ΩAS).
Theorem 20.6 ([AV06b])
Let w = w(v1, . . . , vr ) where the vi ∈ ΩAS (i = 1, . . . , r) and
w ∈ Ωr S. The entropy operator satisﬁes the following inequality:
h(w ) ≤ max{h(w) logm r, h(v1), . . . , h(vr )}. (13)
An ideal I of a semigroup S is said to be prime if st ∈ I
implies s ∈ I or t ∈ I.
Corollary 20.7
The minimum ideal of ΩAS is prime.
240 / 332
Theorem 20.8 ([AV06b])
Let u1, . . . , un ∈ ΩnS and let
(v1, . . . , vn) = [u1, . . . , un]ω
ΩAS
(x1, . . . , xn).
Then the entropy operator satisﬁes the following inequality:
max
1≤i≤m
h(vi ) ≤ max
1≤i≤m
h(ui ).
The following result is a considerable strengthening of
Corollary 20.9.
Corollary 20.9
For m > 1, the set ΩmS \ K(ΩmS) is a subsemigroup of ΩmS
which is closed under composition and iteration.
241 / 332
All the results we have presented involving complexity and
entropy apply to ΩAV with V a pseudovariety containing LSl:
all we require is to be able to test ﬁnite factors, that is sets of
the form (ΩAV)1
w(ΩAV)1
= A∗wA∗, with w ∈ A+
, which we
need to be clopen;
since A∗
wA∗
is LSl-recognizable, such sets are indeed clopen
by Theorem 5.9.
242 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
243 / 332
Some remarks on relatively free profinite
semigroups
Let V be a pseudovariety of semigroups containing
K = [[xωy = xω]].
Recall that the completion mapping ι : A+ → ΩAV is an
injective homomorphism (more generally, whenever N ⊆ V).
We identify each word w ∈ A+ with its image ι(w). The
elements of A+ in ΩAV are called ﬁnite words and the
remaining elements are said to be inﬁnite.
The natural projection pK : ΩAV → ΩAK maps each ﬁnite
word to itself and every inﬁnite pseudoword w to an inﬁnite
word pK(w) ∈ AN (cf. Theorem 21.1), which is called the
inﬁnite preﬁx of w and is denoted −→w .
Dually, if V contains the pseudovariety D = [[xyω = yω]] and
w ∈ ΩAV, then pD(w) is either w, if w is a ﬁnite word, or an
inﬁnite word in AZ− otherwise. In the latter case, we call
pD(w) the inﬁnite suﬃx of w and denote it ←−w .
244 / 332
Hence, if V contains both K and D (whose join can be easily
shown to be the pseudovariety LI), then every inﬁnite
pseudoword w has an inﬁnite preﬁx −→w and an inﬁnite suﬃx
←−w .
Thus, every factorization w = uv in which the factor are both
inﬁnite pseudowords determines a pair (←−u , −→v ) ∈ AZ− × AN of
inﬁnite words.
A ﬁrst natural question is whether every inﬁnite pseudoword
w ∈ ΩAV admits such factorizations.
The following theorem gives a much more precise result. It is
a particular case of a more general phenomenon [Alm95,
Theorem 5.6.1]. The proof presented here could be extended
to the general case.
245 / 332
Theorem 21.1
Let V be an arbitrary pseudovariety and let w ∈ ΩAV be a
pseudoword which does not belong to ι(A+). Then there is some
factorization of the form w = xyωz, with x, y, z ∈ ΩAV.
246 / 332
Proof.
We do not distinguish w ∈ A+
from ι(w) ∈ ΩAV.
To prove the theorem, we claim that the set of all products of the form
xyω
z = xyω
· yω
· yω
z, with x, z ∈ A∗
and y ∈ A+
, is dense in ΩAV \ A+
. The
theorem follows by compactness.
Let w be an element of ΩAV \ A+
. Then there is some sequence (wn)n of
words in A+
such that lim wn = w and lim |wn| = +∞. Given a positive integer
N, consider a complete list of representatives of the classes of isomorphism of
A-generated semigroups from V with at most N elements and let M be the
cardinality of their direct product S. This may be a huge number, but it is
certainly ﬁnite.
Taking n suﬃciently large, we conclude that there is a word v = wn such that
|v| ≥ M and d(w, v) < 2−N
. By construction, S comes equipped with a
(“diagonal”) generating mapping ϕ : A → S. The inequality d(w, v) < 2−N
means that ˆϕ(w) = ˆϕ(v). Now, distributing the homomorphism ˆϕ over the
individual letters that compose the word v, we obtain a product in S of
M = |S| factors. By Lemma 7.1, there is a factorization v = xyz, where
x, z ∈ A∗
and y ∈ A+
, such that ˆϕ(xyω
z) = ˆϕ(v) = ˆϕ(w). Hence
d(w, xyω
z) < 2−N
, which proves the claim.
247 / 332
Corollary 21.2
Let V be an arbitrary pseudovariety. Then every inﬁnite
pseudoword in ΩAV admits factorizations into the product of two
inﬁnite pseudowords.
248 / 332
Regularity in profinite semigroups
An element s of a semigroup S is said to be regular if there
exists t ∈ S such that sts = s.
Recall that two elements of a semigroup S are R-equivalent
(respectively L-equivalent, J -equivalent) if they are preﬁxes
(respectively suﬃxes, factors) of each other.
The equivalence relation D is the smallest such relation
containing both R and L. As a relation, it is the composite
R ◦ L = L ◦ R.
The intersection of the relations R and L is denoted H.
Since R ∪ L ⊆ J , we also have D ⊆ J .
In a proﬁnite semigroup,
(xy)ω
= (xy)ω
x · y(xy)ω−1
= (xy)ω−1
x · y(xy)ω
and so y(xy)ω L (xy)ω R (xy)ωx.
249 / 332
Proposition 21.3
Let S be a proﬁnite semigroup.
(1) If s, t ∈ S are such that st J s then st R s.
(2) If s, t ∈ S are such that st J t then st L t.
(3) The relations J and D coincide in S.
Proof.
(1) Let x, y ∈ S1
be such that s = xsty. Then the equalities s = xn
s(ty)n
hold
for all n ≥ 1, whence so does the equality s = xω
s(ty)ω
. Hence, we have
s = s(ty)ω
= st · y(ty)ω−1
.
The left-right dual statement (2) is proved by dualizing the preceding argument.
(3) Let s, t ∈ S be J -equivalent elements. Then there exist x, y ∈ S1
such
that t = xsy. By (1) and (2), we deduce that
t = xsy R xs L s.
250 / 332
Proposition 21.4
The following conditions are equivalent for a J -class J of a
proﬁnite semigroup S:
(1) there is some idempotent in J;
(2) there is some regular element in J;
(3) all elements of J are regular;
(4) there are some elements s, t ∈ J such that st ∈ J.
The statements of Propositions 21.3 and 21.4 should be
compared with the example in Exercise 1.3.
251 / 332
Proof of Proposition 21.4.
(1) ⇒ (4) and (3) ⇒ (2) are obvious.
(2) ⇒ (1) Suppose that s ∈ J and sts = s for some t ∈ S. Then st
is an idempotent R-equivalent to s, and so J contains idempotents.
(4) ⇒ (3) For such elements s, t ∈ J, Proposition 21.3 entails the
relations t L st R s, whence stx = s and t = yst for some
x, y ∈ S1. It follows that s = stx = systx = sys, whence s is
regular.
For an arbitrary u ∈ J, by Proposition 21.3(3) there exist
v, w, z ∈ S1 such that uv = zs and uvw = u. Hence,
u = uvw = zsvw = zsysvw = u · ysvw, which shows that the
product of u with another element of J belongs to J, and we have
shown that such an element u must be regular.
252 / 332
Proposition 21.5
Let S be a proﬁnite semigroup. Then the Green relations J , R, L,
and H are closed subsets of S × S. In particular, the equivalence
classes for each of these relations are closed sets.
Proof.
The proof for the ﬁrst three relations is similar, while the case of H
follows from H = R ∩ L. Thus, we consider only the case of R.
Suppose that (sn, tn)n is a convergent sequence of pairs of
R-equivalent elements of S and let s = lim sn and t = lim tn. For
each n ≥ 1, there are xn, yn ∈ S1 such that tn = snxn and
sn = tnyn. By compactness, we may assume that the sequences
(xn)n and (yn)n converge. Let x = lim xn and y = lim yn. Then
t = lim tn = lim snxn = sx and s = lim sn = lim tnyn = ty. Hence s
and t are R-equivalent. Taking one of the sequences to be
constant yields that R-classes are closed.
253 / 332
Maximal subgroups
If a subsemigroup of a semigroup S is a group then it is also
called a subgroup of S.
By a maximal subgroup of a semigroup S we mean a subgroup
which is not properly contained in any other subgroup.
Note that all elements of a subgroup G of S are H-equivalent
in G and, therefore, also in S. Hence, every subgroup of S is
contained in the H-class of some idempotent.
Proposition 21.6
Let S be a proﬁnite semigroup.9 Then the maximal subgroups of S
are the H-classes of S that contain idempotents. They are closed
subgroups and, therefore, they are proﬁnite groups.
9
Except for the statements involving topology, the assumption that S is
proﬁnite is superﬂuous but is suﬃcient for our purposes and considerably
simpliﬁes the argument. For the general algebraic result, see, for instance,
[CP61] or [Lal79].
254 / 332
Proof.
Let e be an idempotent of S and let H be its H-class. If s ∈ H,
then there are elements x, y, z, t ∈ S1 such that e = sx = ys and
s = ez = te. It follows that se = es = s and e = s · exe = ete · s.
Hence e is an identity element for H and every every element of H
admits both a left and a right inverse with respect to e by
Proposition 21.3. To show that H is a subgroup of S, it remains to
prove that H is a subsemigroup. Indeed, if s is another element
of H, then yss = es = s and so ss L s again by
Proposition 21.3. By symmetry, we deduce that ss ∈ H. By the
remarks preceding the statement of the proposition, H is a maximal
subgroup and every maximal subgroup must be of this type.
By Proposition 21.5, every H-class is closed, whence maximal
subgroups are closed. Finally, from our deﬁnition of proﬁnite
semigroup, it is immediate that every closed subsemigroup of a
proﬁnite semigroup is also proﬁnite.
255 / 332
Proposition 21.7
Let S be a proﬁnite semigroup. Then all maximal subgroups in the
same D-class are isomorphic.10
Proof.
Let e and f be two D-equivalent idempotents in S and let He and
Hf be their respective H-classes. Let x, y, z, t be such that
exfye = e, exf = zf , and tzf = f . We claim that the mapping ϕ
that sends each h ∈ He to fyhxf is an isomorphism He → Hf . For
h1, h2 ∈ He, we have
fyh1xf · fyh2xf = fyh1 · exfye · h2xf = fyh1h2xf
and ex · fyhxf · ye = exfye · h · exfye = h, so that ϕ is injective.
Similarly, one shows that ϕ is surjective. Since ϕ is continuous, it
is indeed an isomorphism.
10
Again, the purely algebraic statement holds for arbitrary semigroups, but we
treat only the case of interest in these notes.
256 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
257 / 332
Symbolic Dynamics
Let A be a ﬁnite alphabet.
For a function w ∈ AZ, we may sometimes denote by wi the
letter w(i).11 Writing the letters wi in the usual integer order,
we obtain a biinﬁnite word
· · · w−2w−1 · w0w1w2 · · ·
where the · is meant to distinguish an origin for such a word.
Otherwise, just knowing the letters and not the indices, we
will not be able to recover the function w (unless it is
constant) but only a family of such functions, namely all that
can be obtained by placing the origin somewhere.
11
This is avoided when considering sequences of such w.
258 / 332
For w ∈ AZ, we let
σ(w) : Z → A
i → wi+1.
In terms of biinﬁnite words, this operation corresponds to
shifting the origin past one letter to the right. For this reason,
σ is called the shift (function).
w : · · · w−2w−1 · w0w1w2 · · ·
σ(w) : · · · w−2w−1w0 · w1w2 · · ·
For i ≤ j, we write w[i, j] to represent the word wi wi+1 · · · wj .
This is often called a block of w, but we prefer to call it a
ﬁnite factor of w.
259 / 332
Given two inﬁnite words x ∈ AZ− , y ∈ AN we may consider
the biinﬁnite word w ∈ AZ deﬁned by
w(i) =
x(i) if i ∈ Z−
y(i) if i ∈ N.
We denote w by x · y.
We already saw how to multiply a ﬁnite word u by an inﬁnite
word v ∈ AN, namely concatenating u at the beginning of v.
Dually, there is a natural multiplication vu for v ∈ AZ− and
u ∈ A+.
Thus, for instance if 0 < i ≤ j, we have the following
“factorization”for w ∈ AZ, where the notation w(−∞, n] and
w[n, +∞) is self-explanatory:
w = w(−∞, −1] · w[0, i − 1] w[i, j] w[j + 1, +∞).
260 / 332
The mapping
Z → SAZ
n → σn
is a homomorphism into the permutation group of AZ,
deﬁning a natural action of the additive group of integers on
the set AZ.
The set AZ has a proﬁnite structure.
For u, v ∈ AZ deﬁne d(u, v) = 2−r(u,v), where r(u, v) is the
smallest nonnegative integer n such that un = vn or
u−n = v−n. As usual, we put min ∅ = +∞ and 2−∞ = 0.
261 / 332
Exercise 22.1
Show that:
(1) the above function d is an ultrametric on the set AZ;
(2) the inequalities
d σ(u), σ(v) ≤ 2d(u, v)
d σ−1
(u), σ−1
(v) ≤ 2d(u, v)
hold for all u, v, ∈ AZ;
(3) the function σ is a homeomorphism.
262 / 332
Note that, for a real number > 0, the ball of radius
centered at a biinﬁnite word w ∈ AZ, B (w), consists of all
biinﬁnite words v ∈ AZ such that vi = wi for all indices i
satisfying the inequality 2|i| ≥ .
In Symbolic Dynamics, such a set is often called a cylinder.
The reason is that viewing AZ as the product of Z copies of
the set A, the ball B (w) is just the set of all biinﬁnite words
that have the same projection as w in the components
corresponding to the interval [−n, n], where n = − log2 .
Such sets form a basis of the product topology on the set AZ,
where A is viewed with the discrete topology. Thus our metric
has the same open sets as that topology.
263 / 332
In particular, since the alphabet is ﬁnite, the space AZ is
totally bounded.
If (wn)n is a Cauchy sequence of elements of AZ, then, given
k > 0, there is Nk such that, for all n ≥ Nk, the word
wn[−Nk, Nk] is constant. We may deﬁne a biinﬁnite word
w ∈ AZ by letting w(i) = wN|i|
(i). Note that w = lim wn.
Proposition 22.2
The space AZ is complete, whence compact, being totally
bounded.
264 / 332
By a subshift (also known as a shift space, a shift dynamical system,
or simply a shift) we mean a nonempty closed subset of AZ
which is
stable under the action of Z.
The stability condition for a subset X of AZ
is equivalent to
σ(X) ⊆ X and σ−1
(X) ⊆ X.
The space AZ
is also known as the full shift, which explains the
terminology.
For a subshift X ⊆ AZ
, the set of all words of the form w[i, j] with
w ∈ X is called the language of X and it is denoted L(X).
A language L ⊆ A+
is said to be
factorial if it contains all nonempty factors of its members;
prolongable if it is nonempty and, for every u ∈ L there are
letters a, b ∈ A such that au, ub ∈ L.
Proposition 22.3
The correspondence X → L(X) is a bijection between the set of
subshifts X ⊆ AZ and the set of factorial prolongable languages
of A+.
265 / 332
Proof.
From the deﬁnition of L(X), it is clear that L(X) is factorial and
prolongable.
Suppose that L ⊆ A+
is a factorial prolongable language. Let X be the
set of all biinﬁnite words w ∈ AZ
all of whose ﬁnite factors belong to L.
Then X is stable under the action of Z. If w = lim wn is the limit of a
sequence of elements of X, then every ﬁnite factor of w must be a factor
of wn for all suﬃciently large n, whence it belongs to L. Hence X is a
subshift which, by deﬁnition, satisﬁes L(X) ⊆ L. By prolongability, any
word u ∈ L can be extended arbitrarily on both sides, which allows us to
deﬁne, inductively, a biinﬁnite word w all of whose ﬁnite factors lie in L.
Moreover, w must belong to any subshift Y ⊆ AZ
such that L ⊆ L(Y).
Hence u ∈ L(X) and X ⊆ Y for any such Y. Thus L = L(X) and
L(X) ⊆ L(Y) implies X ⊆ Y.
266 / 332
The subshift corresponding to the factorial prolongable
language L ⊆ A+ is denoted XL.
Given a language K ⊆ A+, the exclusion of K is the language
consisting of all words that do not admit any word from K as
a factor.
In other words, the exclusion of K is the language
A+ \ A∗KA∗.
Exercise 22.4
A language is factorial if and only if it is the exclusion of some
language.
267 / 332
Special types of subshifts
A subshift X ⊆ AZ is of ﬁnite type if L(X) is the exclusion of
some ﬁnite language, i.e., the ideal A+ \ L(X) is ﬁnitely
generated.
Equivalently, there is a positive integer n and a set F ⊆ An
such that w ∈ AZ belongs to X if and only if all factors of w
of length n belong to F. The subshift X is then also denoted
by X[F].
From a set K ⊆ An one can build a graph Γ(K) with vertex
set An−1 and an edge u → v if there are letters a, b ∈ A such
that the word ub = av belongs to K.
A word has all its factors of length n in K if and only if the
sequence of its consecutive factors of length n − 1 describe a
path in the graph Γ(K).
A biinﬁnite word belongs to X[F] if and only if the biinﬁnite
sequence of its consecutive factors of length n − 1 determines
a biinﬁnite path in the graph Γ(An \ F).
268 / 332
The graph Γ(An+1) is known as the de Bruijn graph of order n.
Given any ﬁnite directed graph Γ, considering the set of edges
A as an alphabet, the set of all biinﬁnite paths determines a
subshift XΓ ⊆ AZ, which is known as the edge subshift of Γ.
Starting with the subshift of ﬁnite type X[F], every element
w ∈ X[F] determines a biinﬁnite path in Γ(An \ F) and
therefore an element Φ(w) ∈ XΓ(An\F). The correspondence
Φ : X[F] → XΓ(A\F) is easily checked to be a homeomorphism
which commutes with the shift σ.
More generally, for subshifts X ⊆ AZ and Y ⊆ BZ, an
encoding is a continuous function ϕ : X → Y such that the
following diagram commutes:
X
σA
GG
ϕ

X
ϕ

Y
σB
GG Y
A bijective encoding is called a conjugation.
269 / 332
One simple way of constructing encodings is through sliding
windows as above.
Let A and B be two alphabets and let m, n ∈ Z be such that
m + n ≥ 0. Given a function f : Am+n+1 → B we may deﬁne
a function ¯f : AZ → BZ as follows: for w ∈ AZ,
¯f (w)i = f (w[i − m, i + n]).
This is called a sliding block encoding with memory m and
anticipation n.
· · · wi−m−2wi−m−1 wi−m · · · wi−1wi wi+1 · · · wi+n
f


wi+n+1 · · ·
· · · ¯f (w)i−2
¯f (w)i−1
¯f (w)i
¯f (w)i+1 · · ·
If m = n = 1, then the encoding (respectively conjugation) is
said to be a one-block encoding (respectively one-block
conjugation).
270 / 332
Theorem 22.5 (Curtis-Lyndon-Hedlund Theorem)
Every encoding between subshifts is obtained by restriction of a
sliding block encoding.
Proof.
It is an easy exercise to verify that sliding block encodings are
indeed encodings.
Let X ⊆ AZ and Y ⊆ BZ be subshifts over ﬁnite alphabets and
suppose that ϕ : X → Y is an encoding. In particular, ϕ is a
continuous function between compact metric spaces and, therefore,
it is uniformly continuous. Hence, there exists a positive integer n
such that d(w1, w2) < 2−n implies d ϕ(w1), ϕ(w2) < 1
2. This
implies that ϕ(w)0 depends only on the interval w[−n.n] and thus
allows us to deﬁne a function A2n+1 ∩ L(X) → B, which we may
extend arbitrarily to a function f : A2n+1 → B. By construction,
the resulting sliding block encoding ¯f extends ϕ to an encoding
AZ → BZ.
271 / 332
Corollary 22.6
Every conjugation is of the form ϕ ◦ ψ−1, where both ϕ and ψ are
one-block conjugations.
Proof.
By Theorem 22.5, every conjugation ξ : X → Y, with X ⊆ AZ and
Y ⊆ BZ, is obtained by restriction of a sliding block encoding
¯f : AZ → BZ, where f : A2n+1 → B. Consider the one-block
encoding ¯g : (A2n+1)Z → AZ deﬁned by the mapping
g : A2n+1 → A that sends a word of length 2n + 1 to its middle
letter. Let ¯h : (A2n+1)Z → BZ be the one-block encoding deﬁned
by h = f . Then we have ξ = ¯h ◦ ¯g−1|X .
A major open problem in Symbolic Dynamics is to classify the
subshifts of ﬁnite type up to conjugacy. See [LM96] for a
more thorough introduction to this subject and partial results.
272 / 332
A subshift X ⊆ AZ is soﬁc if the language L(X) is regular.
If L ⊆ A+ is a factorial prolongable regular language, then L
may be recognized by a ﬁnite automaton in which every state
is both initial and ﬁnal:
starting from the minimal deterministic ﬁnite automaton
recognizing L, trim it by throwing away all states that either
are not accessible from the initial state or from them no ﬁnal
state is accessible;
then, throw away all states that either are not accessible from
a nontrivial (i.e., having at least one edge) strongly connected
component or from them no such component is accessible;
ﬁnally, make all remaining states both initial and ﬁnal.
Note that, for such an automaton, the subshift XL consists
precisely of the biinﬁnite words w ∈ AZ which can be obtained
by reading the labels of a biinﬁnite path in the automaton.
273 / 332
Examples
Let A = {0, 1} be a two-letter alphabet.
Consider the language F = {11}. The corresponding exclusion
subshift X[F] is known as the golden mean subshift.
It is conjugate to the edge subshift of the following graph
(Γ(A2 \ F)), where the conjugacy (an encoding with memory
0 and anticipation 1) is given by the blue labels:
0 1
01
10
00
274 / 332
The reason for the name given to the subshift is that, if we
consider the adjacency matrix of the above graph,
1 1
1 0
then, as we already observed in another context, the
Perron-Frobenius eigenvalue is precisely the golden mean
1+
√
5
2 . The signiﬁcance of this eigenvalue is that its log2 is the
entropy of the language L(X[F]) = A+ \ A∗11A∗ (deﬁned, for
a language L by inf 1
n log|A| |An ∩ L|).12
12
One can show that the entropy is a conjugacy invariant (see [LM96] and
Section 25).
275 / 332
We may turn the same graph into the following automaton
(where all states are considered both initial and ﬁnal):
0
0
1
The corresponding subshift is known as the even subshift. Its
language L consists of all words over the alphabet A = {0, 1}
such that, in every factor of the form 10n1, n is even.
Thus, A+ \ L is the ideal generated by the (minimum) set
{102n+11 : n ≥ 0}, and therefore it is not ﬁnitely generated.
Hence the even subshift is a soﬁc subshift which is not of
ﬁnite type.
276 / 332
Irreducible subshifts
A language L is irreducible if, for all u, v ∈ L, there exists a
word w such uwv ∈ L.
A subshift X is irreducible if the language L(X) is irreducible.
Note that:
an edge subshift is irreducible if and only if the graph
that deﬁnes it is strongly connected;
a factorial prolongable regular language L is irreducible if
and only if itcan be recognized by a ﬁnite strongly
connected automaton with all states both initial and ﬁnal.
277 / 332
Minimal subshifts
A subshift X ⊆ AZ is minimal if X does not properly contain
another subshift.
For a subshift X ⊆ AZ, and w ∈ X, the closure in AZ of the
orbit O(w) = {σn(w) : n ∈ Z} is a subshift contained in X.
Hence, in a minimal subshift, every orbit is dense.
Thus, for a minimal subshift X, all w ∈ X have the same
ﬁnite factors.
With a little extra eﬀort (exercise!), it follows that every
minimal subshift is irreducible.
A trivial example of minimal subshift is XL, where L consists
of all factors of powers of a ﬁxed word. Such a subshift is
called periodic.
By the pumping lemma, every soﬁc subshift contains some
periodic subshift.
Hence, the only soﬁc minimal subshifts are the periodic ones.
278 / 332
One way to produce minimal subshifts is to iterate primitive
substitutions.
In this context, a substitution is an endomorphism ϕ of a free
semigroup A+. Primitivity has exactly the same meaning as
before.
A primitive substitution ϕ determines a language L(ϕ)
consisting of all words which are factors of some ϕn(a), where
a is a letter.
Since L(ϕ) is clearly factorial and can be easily checked to be
prolongable, it follows that it is the language of a subshift Xϕ.
See [Fog02] for a thorough treatment of subshifts generated
by substitutions and their signiﬁcance in the Theory of
Dynamical Systems.
Before justifying that Xϕ is a minimal subshift, we introduce a
few further useful notions.
279 / 332
For a factorial language L ⊆ A+ and a word u ∈ L, a return
word of u in L is a word v ∈ A+ such that vu ∈ L, u is a
preﬁx of vu, and u only appears as a factor of vu in the preﬁx
and suﬃx positions.
A factorial language L is recurrent if, for every u ∈ L, there is
no inﬁnite word all of whose ﬁnite factors belong to L for
which u is not a factor.
A factorial language L ⊆ A+ is uniformly recurrent if it is
recurrent and, for every u ∈ L, there are only ﬁnitely many
return words of u in L.
In case L is uniformly recurrent, let n be the maximum of the
lengths of the return words of u in L and let N = n + |u|.
Then every word in L of length N contains u as a factor.
Conversely, if there is such an N, then L is uniformly recurrent.
280 / 332
In case the language L is the language of ﬁnite factors of a
biinﬁnite word w ∈ AZ, then we say respectively that u is a
return word for u in w and that w is recurrent or uniformly
recurrent.
Proposition 22.7
Let w ∈ AZ be a biinﬁnite word. Then the subshift O(w) is
minimal if and only if w is uniformly recurrent.
281 / 332
Proof.
We have already observed that a subshift is minimal if and only if all its
elements have the same ﬁnite factors.
(⇒) Suppose that the ﬁnite factor u of w has an inﬁnite sequence uzn of
return words. Without loss of generality, we may assume that the
sequence (zn)n converges in ΩAS, say to a pseudoword z. By the choice
of the words zn, u is not a factor of zn for any n, and therefore it is not a
factor of z. Since z is an inﬁnite pseudoword, by Corollary 21.2, there is a
factorization z = xy, with both x, y inﬁnite. If we glue the inﬁnite suﬃx
of x with the inﬁnite preﬁx of y, we obtain a biinﬁnite word w = ←−x · −→y
all of whose ﬁnite factors are factors of w. Hence w belongs to O(w)
and u should be a factor of w while, by construction, it is not. Thus,
w can only have ﬁnitely many return words of u.
(⇐) Let v ∈ O(w) and let u be a ﬁnite factor of w. We should show
that u is also a factor of v. Let N be such that every factor of w of
length N contains u as a factor. Since d(v, σm
(w)) < 2− N
2 , for
some m, we deduce that u is a factor of v.
282 / 332
Corollary 22.8
Let L ⊆ A+ be a factorial prolongable language. Then the
following conditions are equivalent:
(1) L is recurrent;
(2) L is uniformly recurrent;
(3) L is the language of ﬁnite factors of some minimal subshift.
Proof.
Since L is factorial and prolongable, there is a unique subshift
X ⊆ AZ such that L = L(X)..
(1) ⇒ (3) Since L is recurrent, every w ∈ X must have the same
ﬁnite factors, namely all the words from L, whence X is minimal.
(3) ⇒ (2) follows from Proposition 22.7.
(2) ⇒ (1) is clear from the deﬁnitions.
283 / 332
Corollary 22.9
Let ϕ be a primitive substitution over an alphabet A. Then Xϕ is a
minimal subshift.
Proof.
We verify that the language L(ϕ) is uniformly recurrent.
Let N be such that, for all a, b ∈ A, a appears in the word ϕN(b).
Let u be a word from L(ϕ). Then u is a factor of ϕn(a) for some
n ≥ 1. Every v ∈ L(ϕ) of length
2 max
b∈A
|ϕN+n
(b)| − 1
has some factor of the form ϕN+n(b) = ϕn(ϕN(b)). Since a is a
factor of ϕN(b) and u is a factor of ϕn(a), it follows that u is
factor of v.
284 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
285 / 332
Going profinite
Suppose that L ⊆ A+ is a factorial prolongable language.
The closure L of L in ΩAS provides a natural subset of ΩAS
associated with L.
Since A+ is a discrete subspace of ΩAS (more generally, this
holds for ΩAV for every pseudovariety V containing N by
Proposition 7.3), there is no new ﬁnite word in L, i.e., we have
L ∩ A+ = L.
Hence, symbolic dynamics can also be studied by investigating
suitable closed subset of ΩAS.
Exactly which subsets?
286 / 332
A subset K of a semigroup S is said to be factorial if,
whenever u, v ∈ S are such that u is a factor of v, if
v belongs to K, then so does u.
A subset K ⊆ ΩAS is prolongable if, for every w ∈ K, there
are a, b ∈ A such that aw, wb ∈ K.
Proposition 23.1 ([Cos06, AC09])
Let L ⊆ A+ be a language.
(1) The language L is prolongable in A+ if and only if so is L
in ΩAS.
(2) The language L is factorial in A+ if and only if so is L in ΩAS.
Thus, the suitable closed subsets of ΩAS to study symbolic
dynamics in the proﬁnite world are precisely the closed
factorial prolongable subsets.
The implications (⇐) are both easy.
287 / 332
While the preservation of prolongability is a simple exercise,
the preservation of factoriality is more delicate. The proof
requires some preparation, and it is better to put it in the
right framework, replacing S by a more general pseudovariety
V with suitable properties.
We say that a pseudovariety V is closed under concatenation
if so is the corresponding variety of languages.
A mapping between two metric spaces is said to be open if
the image of every open set is open.
Proposition 23.2 ([AC09, Lemma 2.3])
Let V be a pseudovariety of semigroups containing N. Then V is
closed under concatenation if and only if the multiplication in ΩAV
is an open mapping for every ﬁnite alphabet A.
288 / 332
Proof.
By Theorem 5.9 and Proposition 7.3, a language L over a ﬁnite
alphabet A is V-recognizable if and only if L is open. Hence, if the
multiplication is open and K, L ⊆ A+ are V-recognizable, then
KL = K L is the product of two open sets, i.e., the image under
multiplication of an open subset of ΩAV × ΩAV, whence an open
subset of ΩAV, so that KL is V-recognizable.
Conversely, suppose that V is closed under concatenation. By
Theorems 5.8 and 5.9, every open subset of ΩAV is the union of
sets of the from L, where L ⊆ A+ is V-recognizable. Since
multiplication distributes over union, using again Theorem 5.9, it
suﬃces to show that KL = K L is open in ΩAV whenever
K, L ⊆ A+ are V-recognizable, which follows once more from
Theorem 5.9 since V is closed under concatenation.
289 / 332
Lemma 23.3 ([AC09, Lemma 2.5])
Let S be a metric semigroup and suppose that the multiplication
S × S → S is an open mapping. Let u, v ∈ S and suppose that the
sequence (wn)n converges to uv. Then there is a subsequence
(wnk
)k whose terms admit a factorization wnk
= unk
vnk
such that
lim unk
= u and lim vnk
= v.
Proof.
For each k ≥ 1, the product B1
k
(u) B1
k
(v) of open balls is open.
Hence, it is possible to choose nk such that
wnk
∈ B1
k
(u) B1
k
(v)
and n1 < n2 < n3 < · · · . For each k, there is therefore a
factorization wnk
= unk
vnk
with unk
∈ B1
k
(u) and vnk
∈ B1
k
(v). By
construction, we have lim unk
= u and lim vnk
= v.
290 / 332
Proposition 23.4 ([AC09, Proposition 2.4])
Let V be a pseudovariety closed under concatenation containing N
and let L ⊆ A+ be a factorial language. then the set L is factorial
in ΩAV.
Proof.
Suppose that L ⊆ A+ is a factorial language, w ∈ L, and w = uv
is a factorization in ΩAV. Then there is a sequence (wn)n of
elements of L converging to w. By Lemma 23.3, we may assume
that each wn admits a factorization wn = unvn, with lim un = u
and lim vn = v. By Theorem 21.1, since V contains N, un and vn
must be ﬁnite words and therefore they belong to the factorial
language L. Hence u, v ∈ L. Every factor of w can be obtained
from w in at most a couple of such factorization steps.
291 / 332
The special cases
If L is the complement of a ﬁnitely generated ideal A∗FA∗
of A+, then A∗FA∗ and L are regular languages, A∗FA∗ and L
are clopen subsets of ΩAS and
L = ΩAS \ A∗FA∗ = ΩAS \ (ΩAS)1
F(ΩAS)1
.
Hence L is a clopen subset of ΩAS which is the complement
of a ﬁnitely generated ideal.
Proposition 23.5
Every clopen ﬁnitely generated ideal I of ΩAS is of the form
I = A∗FA∗ for some ﬁnite subset F of A+.
Proof.
By Theorem 5.9, the set J = I ∩ A+ is a regular language such
that J = I. Since A+ is a subsemigroup of ΩAS, J is an ideal
of A+. Since no ﬁnite word admits an inﬁnite pseudoword as a
factor, J must also be ﬁnitely generated.
292 / 332
Thus, subshifts of ﬁnite type over the alphabet A correspond
to the complements of clopen ﬁnitely generated ideals of ΩAS.
Soﬁc subshifts over the alphabet A correspond to clopen
factorial prolongable subsets of ΩAS.
What about irreducible and minimal subshifts?
A subset K of a semigroup S is said to be irreducible if, for all
u, v ∈ K, there is some w ∈ S such that uwv ∈ K.
Proposition 23.6
Let L ⊆ A+ be an arbitrary language. Then L is irreducible in A+
if and only if L is irreducible in ΩAS.
293 / 332
Proof.
(⇒) Given two elements u, v ∈ L, let (un)n and (vn)n be sequences
of elements of L converging, respectively, to u and v. Since L is
irreducible, there is a sequence (wn)n of words such that
unwnvn ∈ L. By compactness, we may assume that (wn)n
converges to some w ∈ ΩAS. By continuity of multiplication, it
follows that uwv ∈ L.
(⇐) Suppose that L is irreducible in ΩAS and let u, v ∈ L. Then
there exists w ∈ ΩAS such that uwv ∈ L. Let (xn)n be a sequence
of words from L converging to uwv. By Lemma 23.3, we may
assume that, for every n ≥ 1, there is a factorization xn = unwnvn
such that lim un = u, lim wn = w, and lim vn = v. Since A+ is a
discrete subsemigroup of ΩAS by Proposition 7.3, we have un = u
and vn = v for all suﬃciently large n. Hence uwnv ∈ L for all
suﬃciently large n.
294 / 332
Proposition 23.7
Let K ⊆ ΩAS be an irreducible subset. Then there is in K some
element w such that every other element of K is a factor of w. In
other words, there is a unique J -class containing elements of K
such that every other such J -class is J -above it. Moreover, this
J -class is regular.
The special J -class of Proposition 23.7 is denoted J (K).
In case K = L(X) for an irreducible subshift X ⊆ AZ, we also
denote J (K) by J (X).
295 / 332
Proof.
Let I be the collection of all closed ideals of ΩAS which have
nonempty intersection with K. Given two such ideals I and J,
there exist u ∈ I ∩ K and v ∈ J ∩ K. Since K is irreducible, there
is some w ∈ ΩAS such that uwv ∈ K. Since I and J are ideals,
uwv belongs to I ∩ J, which shows that I ∩ J ∈ I. By induction on
the number of terms, it follows that the intersection of any ﬁnite
subcollection of I also belongs to I. Hence, again by
compactness, the intersection I = I is a closed ideal of ΩAS
with nonempty intersection with K. Each element of I ∩ K must
generate I, as an ideal, whence they are all J -equivalent and their
J -class is the required one.
Since K is irreducible, if u ∈ I ∩ K, then there is some w ∈ ΩAS
such that uwu ∈ K, whence uwu ∈ I and so uwu J u. By
Proposition 21.4, we conclude that the J -class of u is regular.
296 / 332
Of the special families of subshifts, it remains to consider the
minimal subshifts.
Theorem 23.8 ([Alm05a])
Let X ⊆ AZ be a subshift. Then X is minimal if and only if
L(X) \ A+ is contained in some J -class of ΩAS. Moreover, such a
J -class is a J -maximal regular J -class and every J -maximal
regular J -class of ΩAS contains a set of the form L(X) \ A+ for a
unique minimal subshift X ⊆ AZ.
Recall that every minimal subshift is irreducible.
Note that the J -class containing L(X) \ A+ associated with a
minimal subshift X is precisely the J -class J (X) introduced
earlier for an irreducible subshift.
297 / 332
Proof of Theorem 23.8.
Suppose ﬁrst that the subshift X is minimal. We claim that, if
u ∈ L(X) \ A+ and v ∈ ΩAS \ A+ is such that F(v) ⊆ L(X), then
u is a factor of v. It follows that, for all u, v ∈ L(X) \ A+, u and v
are factors of each other, and so they are J -equivalent. The claim
also entails that every u ∈ L(X) \ A+ is a factor of all its inﬁnite
factors, and so the J -class J of u is J -maximal among J -classes
containing inﬁnite pseudowords. Since, by Theorem 21.1 every
inﬁnite pseudoword has some idempotent factor (or using
Proposition 23.7), the J -class J is regular.
To prove the claim, let (un)n and (vn)n be sequences of elements
of L(X) such that lim un = u and lim vn = v. Since A+ is a
discrete subspace of ΩAS, we have lim |un| = lim |vn| = +∞. By
Proposition 22.7, there is a strictly increasing sequence of indices
(nk)k such that uk is a factor of vnk
. Since ΩAS is a compact
semigroup, it follows that u is a factor of v, as claimed.
298 / 332
(. . . )
Conversely, suppose that the set L(X) \ A+ is contained in a
unique J -class J of ΩAS. To establish that X is minimal, we show
that L(X) is uniformly recurrent. Indeed, otherwise, there would
be a word u ∈ L(X) and a sequence (vn)n of words from L(X)
such that u is not a factor of any of the vn and lim |vn| = +∞. By
compactness, we may assume that (vn)n converges to some
v ∈ ΩAS. Since the language A∗uA∗ is regular, u is not a factor
of v. On the other hand, since the language L(X) is prolongable,
there is also a sequence (un)n of elements of L(X) converging to
some u ∈ ΩAS \ A+ such that u is a factor of each un. Hence u
and v are both inﬁnite pseudowords in L(X) but one has u as
factor and the other does not, which contradicts the assumption
that they are J -equivalent.
299 / 332
(. . . )
Finally, suppose that J is a J -maximal regular J -class of ΩAS and
let L be the language consisting of all ﬁnite factors of the elements
of J. Note that L is factorial and prolongable, whence it is the
language of ﬁnite factors of a unique subshift X ⊆ AZ. By the
usual compactness argument, every element of L \ A+ is a factor of
the elements of J and, therefore, it must belong to J. By the
above, it follows that X is minimal. Since, by the choice of L, it
contains every other subshift Y ⊆ AZ such that L(Y) \ A+ ⊆ J, it
is the only such minimal subshift.
300 / 332
Note that we have also proved the following result.
Corollary 23.9
Let X ⊆ AZ be a minimal subshift. Then a pseudoword w ∈ ΩAS
belongs to J (X) if and only if F(w) = L(X).
A pseudoword w ∈ ΩAS is said to be uniformly recurrent if
the language F(w) is uniformly recurrent.
Corollary 23.10
The uniformly recurrent pseudowords in ΩAS are the elements of
J -maximal regular J -classes.
301 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
302 / 332
Free and projective profinite groups
Let H be a pseudovariety of groups.
Given a pro-H group G, a diagram of the form
G
ϕ

θ
||
H
ψ
GG GG K
(14)
where ϕ is a continuous homomorphism, ψ is a
homomorphism, and H ∈ H, is called an embedding problem
for G.13
A solution of the embedding problem (14) is an onto
continuous homomorphism θ such that the diagram
commutes.
A weak solution of the embedding problem (14) is a
continuous homomorphism θ such that the diagram
commutes.
13
The terminology comes from Galois theory, see [FJ86].
303 / 332
A pro-H group G is said to be H-projective if every
embedding problem (14) has a weak solution.
A G-projective proﬁnite group is also said to be projective.
A pro-H group G is said to be H-free of countable rank if
every embedding problem (14) has a solution.14
Proposition 24.1 ([RZ00, Lemma 7.6.3])
Let H be a pseudovariety of groups.
(1) Every H-projective pro-H group is isomorphic to a closed
subgroup of a free pro-H group.
(2) Suppose that H is closed under extension. Then a pro-H
group is H-projective if and only if it is isomorphic to a closed
subgroup of a free pro-H group.
14
The terminology is justiﬁed by showing that this property is equivalent to G
possessing an universal property similar to freeness, namely being“free on a
(countable) set converging to 1”. See [RZ00] for details.
304 / 332
A pseudovariety of groups H is said to be arborescent if
(H ∩ Ab) ∗ H = H.
Proposition 24.2 ([RZ00, Proposition 7.6.7])
Let H be an arborescent pseudovariety of groups. Then a pro-H
group is projective if and only if it is H-projective.
Theorem 24.3 ([RS08])
Let V be a pseudovariety of semigroups such that
(V ∩ Ab) ∗ V = V. Then every closed subgroup of a free pro-V
semigroup is projective.
305 / 332
Outline
Semigroups of implicit operators
Complexity
Complexity of pseudowords generated by
iteration of substitutions
Entropy
Interlude on profinite semigroups
Symbolic Dynamics
Going profinite
Interlude on profinite groups
Maximal subgroups
306 / 332
Maximal subgroups
Let X ⊆ AZ be an irreducible subshift.
Consider the J -minimal J -class J (X) of ΩAS which contains
elements of L(X) and recall that it is regular.
By Proposition 21.7, all maximal subgroups of ΩAS contained
in J (X) are isomorphic proﬁnite groups. Viewed as an
abstract proﬁnite group, we denote any of them by G(X).
By Theorem 24.3, G(X) is a projective proﬁnite group
associated with the subshift.
By a conjugacy invariant for a class of subshifts we mean a
function deﬁned on that class whose value is the same for
conjugate subshifts.
Theorem 25.1 ([Cos06])
The group G(X) is a conjugacy invariant of the subshift X.
307 / 332
Can one somehow compute these groups?
For the question to make sense from an algorithmic point of
view, both the subshift and the group should be somehow
described by ﬁnite data.
There are two natural families of subshifts described by ﬁnite
data, namely soﬁc subshifts and subshifts deﬁned by the
iteration of primitive substitutions.
308 / 332
The sofic case
In the case of a periodic subshift X, the group G(X) is free
procyclic by Theorem 18.6.
For all other irreducible soﬁc subshifts, the group is in a sense
much larger as stated in the following theorem.
Theorem 25.2 ([CS11])
Let X be a non-periodic irreducible soﬁc subshift. Then the
proﬁnite group G(X) is free of countable rank.
309 / 332
Presentations of profinite groups
By a presentation of a proﬁnite group we mean a pair X; R ,
where X is a set and R is a binary relation on the free
proﬁnite group on the set X.
We only consider here the case where the set of generators X
is a ﬁnite set. Thus, R ⊆ ΩX G × ΩX G.
Usually we write the pairs (u, v) of R as formal equalities
u = v and call them the relations of the presentation.
The presentation is ﬁnite if R is also a ﬁnite set.
Let N be the closed normal subgroup of ΩAG generated by
the elements of the form uv−1 with u = v a relation of the
presentation.
310 / 332
A natural metric on the quotient group ΩX G/N is given by
letting d(uN, vN) = 2−r(u,v), where r(u, v) is the minimum
cardinality of a ﬁnite group G for which there exists a
continuous homomorphism ϕ : ΩX G → G such that
ϕ(N) = {1} and ϕ(u) = ϕ(v).
Exercise 25.3
The quotient group ΩX G/N is proﬁnite for the above metric.
The proﬁnite group thus constructed is called the proﬁnite
group deﬁned by the presentation X; R and is usually also
denoted by X; R .
A proﬁnite group is said to admit the presentation X; R if it
isomorphic to the proﬁnite group X; R .
311 / 332
Proposition 25.4 ([Lub01, AC10])
Every ﬁnitely generated closed subgroup of ΩAS admits a ﬁnite
presentation of the form
X; Φω
(x) = x (x ∈ X)
where Φ is a continuous endomorphism of ΩAG.
We say that an X-generated proﬁnite group G is decidable if,
given any mapping X → H into a ﬁnite group H, there is an
algorithm to determine whether or not ϕ extends to a
continuous homomorphism G → H.
We say that a continuous endomorphism of ΩX G is a ﬁnite
group substitution if it induces an endomorphism of the free
group Ωκ
X G.
312 / 332
Proposition 25.5
Suppose that Φ is a ﬁnite group substitution over a ﬁnite alphabet
X. Then the proﬁnite group X; Φω(x) = x (x ∈ X) is decidable.
We say that a primitive ﬁnite substitution ϕ is periodic if the
subshift Xϕ is periodic.
There is an algorithm to test if a primitive ﬁnite substitution
is periodic [Pan86, HL86].
313 / 332
For a primitive ﬁnite substitution ϕ, we also denote the
J -class J (Xϕ) by J (ϕ) and the proﬁnite group G(Xϕ) by
G(ϕ).
Theorem 25.6 ([AC10])
There is an algorithm that solves the following problem:
Input: a non-periodic primitive ﬁnite substitution over a
ﬁnite alphabet A;
Output: a ﬁnite group substitution Φ over a ﬁnite alphabet X
such that G(ϕ) admits the presentation
X; Φω(x) = x (x ∈ X) .
314 / 332
The generating set X can be explicitly realized in a maximal
subgroup contained in J (ϕ) as follows:
let ba be a two-letter word in L(ϕ) such that ϕω
(a) starts with
a and ϕω
(b) ends with b; such a word ba is called a
connection for ϕ;
let R(ba) be the ﬁnite set of all return words of ba in Xϕ
(which may be eﬀectively computed [Dur98, Alm05a]);
let X = b−1
R(ba)b, which is a code in the sense that it
generates a free subsemigroup of A+
;
by a theorem of Margolis, Sapir and Weil [MSW98], the closed
subsemigroup of ΩAS generated by ϕω
(X) is freely generated
by this set as a proﬁnite semigroup;
by the choice of the word ba, some power ϕN
of ϕ maps X+
into itself;
hence ϕN
induces an endomorphism of X+
which determines a
continuous endomorphism Φ of ΩX G;
a mapping showing that the proﬁnite group G(ϕ) admits the
presentation X; Φω
(x) = x (x ∈ X) is given by
x ∈ X → ϕω
(x).
315 / 332
Corollary 25.7
Let ϕ be a primitive ﬁnite substitution over a ﬁnite alphabet A. Then the
group G(ϕ) is decidable.
A substitution ϕ is said to be proper if all ϕ(a) (a ∈ A) start with
the same letter and all ϕ(a) (a ∈ A) end with the same letter.
Theorem 25.8 ([AC10])
Let ϕ is a proper primitive ﬁnite substitution over a ﬁnite alphabet A.
Then the group G(ϕ) admits the presentation A; ϕω
(a) = a (a ∈ A) .
Theorem 25.9 ([Alm05a])
Let ϕ be a primitive ﬁnite substitution over a ﬁnite alphabet A which
induces an automorphism of the free group Ωκ
AG. Then G(ϕ) is a ﬁnitely
generated free proﬁnite group and the number of generators can be
eﬀectively computed.
316 / 332
Examples
Consider the Fibonacci substitution ϕ(a) = ab, ϕ(b) = a.
Since ϕ induces an automorphism of the free group Ωκ
{a,b}G,
the group G(ϕ) is a free proﬁnite group by Theorem 25.9.
More precisely, the H-class of ϕω(aω) is freely generated by
{ϕω(aba), ϕω(ababa)}.
The reason for this is that a2 is a connection and its return
words are
aab = a · aba · a−1
and a2
bab = a · ababa · a−1
.
Let x = aba and y = ababa. Then ϕ2 maps X+ into itself.
The continuous endomorphism Φ of ΩX G is given by
Φ(x) = xy and Φ(y) = xy2.
Since Φ induces an automorphism of the free group Ωκ
X G, Φω
is the identity mapping and the relations in the presentation
X; Φω(x) = x (x ∈ X) are trivial.
317 / 332
More generally, we have the following result.
A subshift X over a two-letter alphabet A is said to be
Sturmian if |L(X)| ∩ An = n + 1. Equivalently, every
w ∈ L(X) \ A+ is Sturmian.
Theorem 25.10 ([Alm05a, Corollary 6.1])
Let X be any Sturmian subshift. Then G(X) is a free proﬁnite
group on two generators.
The proof of this result was obtained by a suitable
approximation of an arbitrary Sturmian subshift by Sturmian
subshifts generated by substitutions.
318 / 332
A non-free profinite maximal subgroup
Consider the proper substitution deﬁned by ϕ(a) = ab and
ϕ(b) = a3b.
The only connection for ϕ is the word ba, whose return words
are ba and ba3 and so X = {ab, a3b}.
Letting x = ab and y = a3b and taking N = 1, the
continuous endomorphism Φ of the free group Ωκ
X G is given
by Φ(x) = xy and Φ(y) = x3y, that is, it looks exactly like
the original substitution.
The maximal subgroup H of ΩAS containing ϕω(X) is also
generated by {ϕω(a), ϕω(b)}.
By Theorem 25.8, the group G(ϕ) admits the presentation
a, b; ϕω
(a) = a, ϕω
(b) = b .
One can use it to prove the following result.
319 / 332
Theorem 25.11 ([AC10])
For the above proper substitution, the group G(ϕ) is not H-free
for any pseudovariety of groups H.
Proof.
Suppose ﬁrst that H is free on a pseudovariety H containing the two element
additive group Z/2Z. Since {ϕω
(a), ϕω
(b)} generates H, it freely generates H
as a pro-H group. Hence the mapping that sends both ϕω
(a) and ϕω
(b) to 1
extends to an onto continuous homomorphism H → Z/2Z. But it sends both
generators ϕω
(ab) and ϕω
(a3
b) to 0, and so it should be a constant mapping.
Hence, H is not free pro-H for any pseudovariety containing Z/2Z. To
conclude the proof, it suﬃces to show that H has a ﬁnite continuous image of
even order. We claim that in fact the alternating group A5 is such an image.
To prove the claim, it suﬃces to show that the generating 3-cycles α = (1 2 3)
and β = (3 4 5) verify the deﬁning relations for our presentation, i.e., that
(α, β) is a periodic point of the implicit operator [ab, a3
b]A5 . Indeed, direct
calculation shows that it has period 12 for this operator.
320 / 332
The case of the Prouhet-Thue-Morse
substitution
To conclude, consider the Prouhet-Thue-Morse substitution
τ(a) = ab, τ(b) = ba.
All two-letter words are connections for τ. We choose a2.
The return words of a2 in Xτ are
aababb, aababbab, aabb, aabbab and the set X consists of the
words
x = ab2
a, y = abab2
a, z = ab2
aba, t = abab2
aba.
The subsemigroup X+ is stabilized by τ2.
Let α = τω(x), β = τω(y), γ = τω(z), and δ = τω(t).
A simple calculation shows that βα−1γ = δ, and so the group
H-class H of ϕω(a2) is generated by {α, β, γ}. Moreover the
substitution on X+ associated with τ2 is given by
Φ(x) = zxy, Φ(y) = ztxy, Φ(z) = zxty, Φ(t) = ztxty.
321 / 332
By Theorem 25.6 and the description of the algorithm
following it, H admits the presentation
x, y, z, t; Φω
(u) = u (u = x, y, z, t) .
Taking account the equality βα−1γ = δ, we may eliminate the
generator t, expressing Φ only in terms of the three remaining
generators to obtain the presentation
x, y, z; Ψω
(u) = u (u = x, y, z)
where Ψ(x) = zxy, Ψ(y) = zyx−1zxy, and Ψ(z) = zxyx−1zy.
One may use similar techniques to those described in the
proof of Theorem 25.11 to prove that H cannot be generated
by fewer than three elements and also the following result.
Theorem 25.12 ([AC10])
The proﬁnite group G(τ) is not H-free for any pseudovariety of
groups H.
322 / 332
Final remarks
Although we have an algorithm to determine if a ﬁnite group
is a quotient of G(τ), we still do not know whether the
pseudovariety generated by all ﬁnite quotients of this proﬁnite
group is G.
We also do not know if the proﬁnite group G(X) of a minimal
subshift X is always decidable.
Finally, we do not know if there is any proﬁnite group of the
form G(X) which is not free but which is H-free for some
proper pseudovariety of groups H.
Much of the connections with symbolic dynamics presented in
Part 3 of the lectures carry over to pseudovarieties V
containing LSl. Of course, when groups are involved, the
results further depend on the intersection V ∩ G. For instance,
if H = V ∩ G is commutative and satisﬁes a pseudoidentity of
the form xp = 1, where p is prime, then every group in ΩAV
is free pro-H, being a vector space over the ﬁeld Z/pZ.
323 / 332
References
[ABR92] D. Albert, R. Baldinger, and J. Rhodes, The identity problem for ﬁnite
semigroups (the undecidability of), J. Symbolic Logic 57 (1992), 179–192.
[AC09] J. Almeida and A. Costa, Inﬁnite-vertex free proﬁnite semigroupoids and
symbolic dynamics, J. Pure Appl. Algebra 213 (2009), 605–631.
[AC10] , Presentations of Sch¨utzenberger groups of minimal subshifts,
Tech. Report CMUP 2010-1, Univ. Porto, 2010.
[AE03] J. Almeida and A. Escada, Semidirect products with the pseudovariety of
all ﬁnite groups, Proceedings of the International Conference Words,
Languages and Combinatorics (Kyoto, March, 2000) (Singapore) (M. Ito
and T. Imaoka, eds.), World Scientiﬁc, 2003, pp. 1–21.
[Alm95] J. Almeida, Finite semigroups and universal algebra, World Scientiﬁc,
Singapore, 1995, English translation.
[Alm02] , Dynamics of implicit operations and tameness of pseudovarieties
of groups, Trans. Amer. Math. Soc. 354 (2002), 387–411.
[Alm05a] , Proﬁnite groups associated with weakly primitive substitutions,
Fundamentalnaya i Prikladnaya Matematika (Fundamental and Applied
Mathematics) 11 (2005), no. 3, 13–48, In Russian. English version in J.
Math. Sciences 144, No. 2 (2007) 3881–3903.
324 / 332
[Alm05b] , Proﬁnite semigroups and applications, Structural Theory of
Automata, Semigroups, and Universal Algebra (New York) (Valery B.
Kudryavtsev and Ivo G. Rosenberg, eds.), NATO Science Series II:
Mathematics, Physics and Chemistry, vol. 207, Springer, 2005,
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, pp. 1–45.
[AS00a] J. Almeida and B. Steinberg, On the decidability of iterated semidirect
products and applications to complexity, Proc. London Math. Soc. 80
(2000), 50–74.
[AS00b] , Syntactic and global semigroup theory, a synthesis approach,
Algorithmic Problems in Groups and Semigroups (J. C. Birget, S. W.
Margolis, J. Meakin, and M. V. Sapir, eds.), Birkh¨auser, 2000, pp. 1–23.
[AS01] J. Almeida and P. V. Silva, SC-hyperdecidability of R, Theor. Comp. Sci.
255 (2001), 569–591.
[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.
325 / 332
[AT01] J. Almeida and P. G. Trotter, The pseudoidentity problem and reducibility
for completely regular semigroups, Bull. Austral. Math. Soc. 63 (2001),
407–433.
[AV06a] J. Almeida and M. V. Volkov, Subword complexity of proﬁnite words and
subgroups of free proﬁnite semigroups, Int. J. Algebra Comput. 16 (2006),
221–258.
[AV06b] , Subword complexity of proﬁnite words and subgroups of free
proﬁnite semigroups, Int. J. Algebra Comput. 16 (2006), 221–258.
[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.
[Ber79] J. Berstel, Transductions and context-free languages, B. G. Teubner,
Stuttgart, 1979.
[BS73] J. A. Brzozowski and I. Simon, Characterizations of locally testable
events, Discrete Math. 4 (1973), 243–271.
[Cos06] A. Costa, Conjugacy invariants of subshifts: an approach from proﬁnite
semigroup theory, Int. J. Algebra Comput. 16 (2006), 629–655.
[CP61] A. H. Cliﬀord and G. B. Preston, The algebraic theory of semigroups,
vol. I, Amer. Math. Soc., Providence, R.I., 1961.
326 / 332
[CS11] A. Costa and B. Steinberg, Proﬁnite groups associated to soﬁc shifts are
free., Proc. London Math. Soc. 102 (2011), 341–369.
[CT04] J. C. Costa and M. L. Teixeira, Tameness of the pseudovariety LSl, Int. J.
Algebra Comput. 14 (2004), 627–654.
[Del01] M. Delgado, On the hyperdecidability of pseudovarieties of groups, Int. J.
Algebra Comput. 11 (2001), 753–771.
[Dur98] F. Durand, A characterization of substitutive sequences using return
words, Discrete Math. 179 (1998), no. 1-3, 89–101.
[Eil76] S. Eilenberg, Automata, languages and machines, vol. B, Academic Press,
New York, 1976.
[ELR75] A. Ehrenfeucht, K. P. Lee, and G. Rozenberg, Subword complexities of
various classes of deterministic developmental languages without
interaction, Theor. Comp. Sci. 1 (1975), 59–75.
[FJ86] M. D. Fried and M. Jarden, Field arithmetic, Springer, Berlin, 1986.
[Fog02] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and
combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag,
Berlin, 2002.
[GAP06] The GAP Group, GAP – Groups, Algorithms, and Programming, Version
4.4, 2006, (http://www.gap-system.org).
327 / 332
[Hal50] M. Hall, A topology for free groups and related groups, Ann. Math. 52
(1950), 127–139.
[Hen88] Karsten Henckell, Pointlike sets: the ﬁnest aperiodic cover of a ﬁnite
semigroup, J. Pure Appl. Algebra 55 (1988), 85–126.
[HL86] T. Harju and M. Linna, On the periodicity of morphisms on free monoids,
RAIRO Inf. Th´eor. et Appl. 20 (1986), 47–54.
[HM38] G. A. Hedlund and M. Morse, Symbolic dynamics, Amer. J. Math. 60
(1938), 815–866.
[HMPR91] K. Henckell, S. Margolis, J.-E. Pin, and J. Rhodes, Ash’s type II theorem,
proﬁnite 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 Scientiﬁc, 1991, pp. 453–463.
[Hun83] R. P. Hunter, Some remarks on subgroups deﬁned by the Bohr
compactiﬁcation, Semigroup Forum 26 (1983), 125–137.
[Hun88] , Certain ﬁnitely generated compact zero-dimensional semigroups,
J. Austral. Math. Soc., Ser. A 44 (1988), 265–270.
[KM02] I. Kapovich and A. Myasnikov, Stallings foldings and subgroups of free
groups, J. Algebra 248 (2002), 608–668.
328 / 332
[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 ﬁnite semigroups and machines, Trans. Amer.
Math. Soc. 116 (1965), 450–464.
[Lal79] G. Lallement, Semigroups and combinatorial applications,
Wiley-Interscience, J. Wiley & Sons, Inc., New York, 1979.
[LM96] D. Lind and B. Marcus, An introduction to symbolic dynamics and
coding, Cambridge University Press, Cambridge, 1996.
[Lub01] A. Lubotzky, Pro-ﬁnite presentations, J. Algebra 242 (2001), 672–690.
[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 ﬁnite monoids and topology for
the free monoid, Proc. 1984 Marquette Semigroup Conference
(Milwaukee), Marquette University, 1984, pp. 113–129.
[MP87] , Inverse semigroups and varieties of ﬁnite semigroups, J. Algebra
110 (1987), 306–323.
329 / 332
[MS93] F. Mignosi and P. S´e´ebold, Morphismes sturmiens et r`egles de rauzy, J.
Th´eor. Nombres Bordeaux 5 (1993), 221–233.
[MSW98] S. Margolis, M. Sapir, and P. Weil, Irreducibility of certain
pseudovarieties, Comm. Algebra 26 (1998), 779–792.
[MSW01] , Closed subgroups in pro-V topologies and the extension problem
for inverse automata, Int. J. Algebra Comput. 11 (2001), 405–445.
[Num57] K. Numakura, Theorems on compact totally disconnetced semigroups and
lattices, Proc. Amer. Math. Soc. 8 (1957), 623–626.
[Pan84] J.-J. Pansiot, Complexit´e des facteurs des mots inﬁnis engendr´es par
morphismes it´er´es, Automata, Languages and Programming (Antwerp,
1984) (Berlin), Lect. Notes Comput. Sci., no. 172, Springer, 1984,
pp. 380–389.
[Pan86] , Decidability of periodicity for inﬁnite words, RAIRO Inf. Th´eor.
et Appl. 20 (1986), 43–46.
[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.
[Pro51] E. Prouhet, M´emoire sur quelques relations entre les puissances des
nombres, C. R. Acad. Sci. Paris 33 (1851), 31.
330 / 332
[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 Birkhoﬀ theorem for ﬁnite algebras, Algebra Universalis
14 (1982), 1–10.
[RS08] J. Rhodes and B. Steinberg, Closed subgroups of free proﬁnite monoids
are projective proﬁnite groups, Bull. London Math. Soc. 40 (2008), no. 3,
375–383.
[RZ93] L. Ribes and P. A. Zalesski˘ı, On the proﬁnite topology on a free group,
Bull. London Math. Soc. 25 (1993), 37–43.
[RZ00] , Proﬁnite groups, Ergeb. Math. Grenzgebiete 3, no. 40, Springer,
Berlin, 2000.
[Sch65] M. P. Sch¨utzenberger, On ﬁnite 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.
[Sta83] J. R. Stallings, Topology of ﬁnite graphs, Inventiones Mathematicae 71
(1983), 551–565.
331 / 332
[Ste01] B. Steinberg, Inevitable graphs and proﬁnite topologies: some solutions to
algorithmic problems in monoid and automata theory, stemming from
group theory, Int. J. Algebra Comput. 11 (2001), 25–71.
[Ste11] , On the endomorphism monoid of a proﬁnite semigroup, Portugal.
Math. 68 (2011), 177–183.
[Sti73] P. Stiﬄer, Extension of the fundamental theorem of ﬁnite semigroups,
Advances in Math. 11 (1973), 159–209.
[Thu06] A. Thue, ¨Uber unendlichen zeichenreihen, Kra. Vidensk. Selsk. Skrifter, I.
Mat. Nat. Kl. (1906), no. 7, 1–22.
[Thu12] A. Thu¨e, ¨Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen,
Norske Vid. Selsk. Skr. I. Mat.-nat. Kl., Christiana 1 (1912), 1–67.
[ˇS63] A. I. ˇSirˇsov, On certain near-engel groups, Algebra i Logika 2 (1963),
no. 5, 5–18.
[Zor36] M. Zorn, Nilpotency of ﬁnite groups (abstract), Bull. Amer. Math. Soc.
42 (1936), 485–486.
332 / 332