Outline
Language recognition devices
Eilenberg’s correspondence
Decidable pseudovarieties
Metrics associated with pseudovarieties
Pro-V semigroups
Reiterman’s Theorem
Examples of relatively free profinite semigroups
Pseudowords as operations
Implicit signatures
70 / 113
N: finite nilpotent semigroups
Recall that N = [[xω
= 0]] = n≥1[[x1 · · · xn = 0]].
The proof depends on the following key result.
Lemma 7.1
Let S be a finite semigroup with n elements. Then, for every choice of
elements s1, . . . , sn ∈ S, there exist indices i, j such that 0 ≤ i < j ≤ n
and the following equality holds for all k ≥ 1:
s1 · · · sn = s1 · · · si (si+1 · · · sj )k
sj+1 · · · sn.
Proof.
Consider the n products pr = s1 · · · sr (r = 1, . . . , n). If they are all distinct,
then at least one of them, say pr , is idempotent and we may take i = 0, j = r.
Otherwise, there are indices i, j such that 1 ≤ i < j ≤ n and pi = pj , in which
case pi = pj = pi si+1 · · · sj = pi (si+1 · · · sj )k
.
71 / 113
Let ϕ : A+
→ S be a homomorphism into a semigroup S ∈ N, say
satisfying x1 · · · xn = 0. Then, all words of length at least n belong
to ϕ−1
(0) and for s ∈ S \ {0}, the words in the language
L = ϕ−1
(s) have length less than n, and so L is a finite set.
Thus, every N-recognizable language is either finite or cofinite.
To show that these are precisely the N-recognizable languages, it
suffices to show that every singleton language {w} ⊆ A+
is
N-recognizable.
Let n = |w| be the length of the word w. Consider the semigroup S
consisting of the words of A+
of length at most n together with a
zero element 0. The product of two words is the word resulting from
their concatenation if that word has length at most n and is 0
otherwise.1
Then S satisfies the identity x1 · · · xn = 0, for the
natural homomorphism ϕ : A+
→ S, that sends each letter to itself,
we have ϕ−1
(w) = {w}.
1
This amounts to“killing”the ideal of the semigroup A+
consisting of the
words of length greater than n, identifying all the elements in the ideal to a
zero. In semigroup theory, such a construction is called a Rees quotient.
72 / 113
Proposition 7.2
A language over a finite alphabet A is N-recognizable if and only if
it is finite or its complement in A+ is finite.
In view of Theorem 5.9, we deduce the following result:
Proposition 7.3
Let V be a pseudovariety of semigroups containing N. Then the
completion homomorphism ι : A+ → ΩAV is injective and A+ is a
discrete subspace of ΩAV. In particular, a language L ⊆ A+ is
V-recognizable if and only if its closure L in ΩAV is a clopen
subset.
73 / 113
Proof.
The injectivity of ι amounts to V satisfying no identity u = v with
u, v ∈ A+ distinct words. Indeed, Synt({u}) is nilpotent, whence it
belongs to V. Since 1u1 ∈ {u} while 1v1 /∈ {u}, we deduce that u
and v are not σ{u}-equivalent and so Synt({u}) |= u = v.
We may therefore identify each w ∈ A+ with ι(w) ∈ ΩAV.
For w ∈ A+, we have {w} = {w}, because ΩAV is a metric space.
Since {w} is V-recognizable, its closure {w} is an open subset
of ΩAV by Theorem 5.9. Hence A+ is a discrete subset
of ΩAV.
74 / 113
Proposition 7.4
The semigroup ΩAN is obtained by adding to A+ a zero element.
The open sets containing zero consist of zero together with a
cofinite subset of A+.2
Proof.
It suffices to observe that a non-eventually constant sequence
(wn)n of words of A+ is a Cauchy sequence with respect to the
metric dN if and only if lim |wn| = ∞. In the affirmative case, for
every homomorphism ϕ : A+ → S into S ∈ N, we have
lim ϕ(wn) = 0. Thus, all non-eventually constant Cauchy
sequences converge to the same point ot ΩAN, which is a zero.
The open subsets of ΩAN containing 0 have complement which is
a closed, whence compact, subset of A+. Since A+ is a discrete
subset of ΩAN, that complement must be finite. The converse is
clear.
2
This is known as the Alexandroff or one-point compactification, which in
general is obtained by adding one point and declaring the open sets containing
it to consist also of the complement of a compact subset of the original space.
75 / 113
K: finite semigroups satisfying es = e
Recall that K = [[xω
y = xω
]]. Note that
K =
n≥1
Kn where Kn = [[x1 · · · xny = x1 · · · xn]].
Let AN
denote the set of all right infinite words over A, i.e.,
sequences of letters.
Endow the set S = A+
∪ AN
with the operation
u · v =
uv if u ∈ A+
u otherwise
and the function d : S × S → R≥0 defined by d(u, v) = 2−r(u,v)
,
where r(u, v) is the length of the longest common prefix of u and v.
76 / 113
Proposition 7.5
The set S is a pro-K semigroup for the above operation and distance
function d. The unique continuous homomorphism ΩAK → S that sends each
letter a ∈ A to itself is an isomorphism.
Proof.
It is easy to check that the multiplication defined on S is associative and that d
is an totally bounded complete ultrametric.
Consider the set Sn consisting of all words of A+
of length at most n, endowed
with the operation
u · v =
uv if |uv| ≤ n
in(u) otherwise
where in(w) denotes the longest prefix of length at most n of the word w. This
operation is associative and Sn ∈ Kn. Moreover, every n-generated semigroup
from Kn is a homomorphic image of Sn. Hence Sn ΩAKn.
Note also that the mapping ϕn : S → Sn which sends each w ∈ S to in(w) is a
continuous homomorphism.
Hence, given two distinct points u and v from S, for n = r(u, v) + 1, the
mapping ϕn is a continuous homomorphism into a semigroup from K which
distinguishes u from v. Thus, S is a pro-K semigroup.
77 / 113
(. . . )
Consider next the unique continuous homomorphism ψ : ΩAK → S which maps
each letter a ∈ A to itself. Since K = n≥1 Kn, given distinct u, v ∈ ΩAK,
there exists a continuous homomorphism θ : ΩAK → Sn such that θ(u) = θ(v).
ΩAK
ψ
GG
θ

S
ϕn

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

S
ϕ

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

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

ϕ◦f
ι

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

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

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