Pointlike reducibility of pseudovarieties
of the form V ∗ D

arXiv:1509.04088v2 [] 2 Mar 2016

J. C. Costa

C. Nogueira

M. L. Teixeira

December 2, 2015

Abstract
In this paper, we investigate the reducibility property of semidirect products of the
form V ∗ D relatively to (pointlike) systems of equations of the form x1 = · · · = xn , where
D denotes the pseudovariety of definite semigroups. We establish a connection between
pointlike reducibility of V ∗ D and the pointlike reducibility of the pseudovariety V. In
particular, for the canonical signature κ consisting of the multiplication and the (ω − 1)power, we show that V ∗ D is pointlike κ-reducible when V is pointlike κ-reducible.
Keywords. Semigroup, pseudovariety, semidirect product, implicit signature, pointlike,
equations, reducibility.

1

Introduction

Since its introduction in the 1970’s by Eilenberg [13], the notion of a pseudovariety has played
a key role in the classification of finite semigroups. Recall that a pseudovariety of semigroups
(in general, of algebras of any finitary type) is a class of finite semigroups (resp. of finite
algebras of that type) which is closed under taking subsemigroups (resp. subalgebras), homomorphic images and finite direct products. A pseudovariety is said to be decidable if there
is an algorithm to test membership of a given finite semigroup in that pseudovariety. One
of the main motivations to study decidability of pseudovarieties comes from its applications
in computer science, where the characterization of some combinatorial events associated with
rational languages, finite automata or various kinds of logical formalisms is reduced to such
membership problem [13, 15, 16, 23]. Due to the Krohn-Rhodes decomposition theorem [14],
the decidability of semidirect products of pseudovarieties has received particular attention.
J. C. Costa & M. L. Teixeira: CMAT, Dep. Matemática e Aplicações, Universidade do Minho, Campus
de Gualtar, 4700-320 Braga, Portugal; e-mail: jcosta@math.uminho.pt, mlurdes@math.uminho.pt
C. Nogueira: CMAT, Escola Superior de Tecnologia e Gestão, Instituto Politécnico de Leiria, Campus 2,
Morro do Lena, Alto Vieiro, 2411-901 Leiria, Portugal; e-mail: conceicao.veloso@ipleiria.pt

1

2

J. C. Costa, C. Nogueira, M. L. Teixeira

The semidirect products of the form V ∗ D, where D is the pseudovariety of all finite
semigroups in which idempotents are right zeros, are among the most studied [20, 22, 3, 4].
For a pseudovariety V of monoids, LV denotes the pseudovariety of all finite semigroups S
whose local submonoids are in V (i.e., eSe ∈ V for all idempotents e of S). It is well-known [13]
that V ∗ D is a subpseudovariety of LV. In addition, it is known from work by Straubing [20],
Thérien and Weiss [21] and Tilson [22] that the equality V ∗ D = LV holds if and only if the
pseudovariety V is local (in the sense of Tilson [22]). We have, for instance, the equalities
Sl ∗ D = LSl and G ∗ D = LG, where Sl and G stand for the pseudovarieties of semilattices
and groups respectively. In the 1970’s, Henckell and Rhodes introduced the notion of a Vpointlike set as a subset of a finite semigroup that is related to a point under every relational
morphism with a member of the pseudovariety V. One says that V has decidable pointlikes
if one can effectively compute all the V-pointlike sets of any given finite semigroup. The
question of decidability of V-pointlike sets can be translated into a question of decidability of
the pseudovariety V, since a finite semigroup S is in V if and only if its V-pointlike subsets
are singletons. The Delay Theorem of Tilson [22] establishes that a pseudovariety of the form
V∗D is decidable if and only if gV, the pseudovariety of categories generated by V, is decidable
and that a semigroup of delay n is in V ∗ D if and only if it is in V ∗ Dn . In [19], Steinberg
proves a Generalized Delay Theorem which generalizes the Delay Theorem of Tilson from a
result about membership to a result about pointlikes. He shows that the V ∗ D-pointlikes of
a semigroup of delay n are precisely its V ∗ Dn -pointlikes and that if a pseudovariety V has
decidable pointlikes then so does V ∗ D.
Since the semidirect product operator does not preserve decidability [17, 11], some authors
have been exploring the idea of establishing stronger properties of the factors under which the
semidirect product is necessarily decidable [2, 18]. At present no satisfactory such properties
have been found. The key property which intervenes in a partially successful approach, has
been formulated (and called reducibility) by Almeida and Steinberg [8] as an extension of seminal work by Ash [10] on the pseudovariety G (where the key property was called inevitability).
The reducibility property was originally formulated in terms of graph equation systems and
latter extended by Almeida [2] under the designation of complete reducibility, and independently by Rhodes and Steinberg [18] under the designation of inevitable substitutions, to any
system of equations, since different kinds of systems appear when different pseudovariety operators are considered. The reducibility property is parameterized by an implicit signature
σ (a set of implicit operations on semigroups containing the multiplication), and we talk of
σ-reducibility. Informally speaking, a pseudovariety V is said to be σ-reducible relatively to
an equation system Σ with rational constraints when the existence of a solution of the system
by implicit operations over V implies the existence of a solution of Σ given by σ-terms over V
and satisfying the same constraints. The pseudovariety V is said to be pointlike σ-reducible
if it is σ-reducible relatively to every system of equations of the form x1 = x2 = · · · = xn ,
and it is called σ-reducible if it is σ-reducible with respect to every graph equation system.
For pseudovarieties of aperiodic semigroups it is common to use the signature ω consisting of

Pointlike reducibility of pseudovarieties of the form V ∗ D

3

the multiplication and the ω-power. For instance, ω-reducibility was already established for
the pseudovarieties D [9], LSl [12] and R [6] of all finite R-trivial semigroups and pointlike
ω-reducibility was recently proved by the first author with Almeida and Zeitoun [7] for the
pseudovarieties A of all finite aperiodic semigroups and DA of all finite semigroups in which
all regular elements are idempotents. The ω-reducibility of A and DA remain to be investigated, although it is natural to presume that the method in the proof of ω-reducibility of R
should apply to DA with minor adaptations.
In this paper, we focus on semidirect products of the form V ∗ D in order to analyze connections between their pointlike reducibility and the pointlike reducibility of the pseudovariety
V. We show that pointlike reducibility of V can be converted into pointlike reducibility of the
pseudovariety V∗D. To be more precise, under mild hypotheses on an implicit signature σ, we
prove that if V is pointlike σ-reducible then V ∗ D is pointlike σ-reducible. As an application,
we deduce that V ∗D is pointlike κ-reducible when V is pointlike κ-reducible, where κ denotes
the canonical signature consisting of the multiplication and the (ω − 1)-power. Our starting
point is the paper [5] of the first and third authors in collaboration with Almeida, where a
similar study was performed for semidirect products with an order-computable pseudovariety
and various kinds of reducibility properties. For each positive integer k, the pseudovariety Dk
S
defined by the identity yx1 · · · xk = x1 · · · xk is order-computable, and k Dk = D. We use
results of [5] concerning the pseudovarieties Dk to derive our results relative to D and the
pointlike reducibility property. The study of the reducibility (for graph equation systems) of
the pseudovarieties V ∗ D should be the natural sequence of our work, but this appears to be
much more challenging. Our expectation is that it may be possible to combine the techniques
of this paper with the solution already known [12] for the case of the pseudovariety Sl ∗ D, if
not for the general case V ∗ D at least for some specific cases.

2

Preliminaries

This section introduces briefly most essential preliminaries, and some terminology and notation. We assume familiarity with basic results of the theory of semigroup pseudovarieties and
implicit operations. For further details and general background see [1, 2, 18].
Throughout this paper, A denotes a finite set. For a pseudovariety V of semigroups, a
pro-V semigroup is a compact semigroup which is residually in V. We denote by ΩA V the
pro-V semigroup freely generated by the set A: for each pro-V semigroup S and each function
ϕ : A → S, there is a unique continuous homomorphism ϕ : ΩA V → S extending ϕ. The elements of ΩA V, usually called pseudowords over V, are naturally interpreted as A-ary implicit
operations on V (mappings S A → S, with S ∈ V, that commute with homomorphisms). The
subsemigroup generated by A is denoted by ΩA V. When ΩA V is finite and effectively computable, the pseudovariety V is said to be order-computable. If V′ is another pseudovariety
and V ⊆ V′ , then there is a unique continuous homomorphism pA,V′ ,V : ΩA V′ → ΩA V, called
the natural projection, mapping the generators of ΩA V′ to the generators of ΩA V. When V′

4

J. C. Costa, C. Nogueira, M. L. Teixeira

is the pseudovariety S of all finite semigroups, we will usually abbreviate the notation of the
homomorphism pA,V′ ,V by writing simply pV . A pseudoidentity is a formal equality π = ρ
with π, ρ ∈ ΩA S. We say that a pseudovariety V satisfies the pseudoidentity π = ρ, and write
V |= π = ρ, if ϕπ = ϕρ for every continuous homomorphism ϕ : ΩA S → S into a semigroup
S ∈ V, which is equivalent to saying that pV π = pV ρ.
Given an element s of a compact topological semigroup, the closed subsemigroup generated
by s contains a unique idempotent, denoted sω . For each q ∈ N, the element sω+q (= sω sq )
belongs to the maximal closed subgroup containing sω , and its group inverse is denoted by
sω−q . As one notices easily sω−q = (sq )ω−1 = (sω−1 )q . For a given finite semigroup S, let
k be an integer greater than |S| and let s1 , . . . , sk ∈ S. Then there are integers i and j
such that 1 < i ≤ j ≤ k and s1 · · · si−1 = s1 · · · si−1 (si . . . sj )m for every m ∈ N, whence
s1 · · · si−1 = s1 · · · si−1 (si . . . sj )ω+1 .
The following is a list of pseudovarieties we will use in this paper, each of them defined by
a single pseudoidentity and where k ∈ N:
K = Jxω y = xω K,
Kk = Jx1 · · · xk y = x1 · · · xk K,
ω
ω
D = Jyx = x K,
Dk = Jyx1 · · · xk = x1 · · · xk K,
ω
ω
ω
LI = Jx yx = x K.
For a positive integer k, let Ak = {w ∈ A+ : |w| = k} be the set of words over A with
length k and let Ak = A1 ∪· · ·∪Ak = {w ∈ A+ : |w| ≤ k} be the set of non-empty words over A
with length at most k. It is easy to observe that both ΩA Kk and ΩA Dk may be identified with
Ak and that the product is defined by u · v = ik (uv) in ΩA Kk and by u · v = tk (uv) in ΩA Dk ,
where ik w and tk w denote respectively the longest prefix and the longest suffix of length at
most k of a given word w. So, Kk and Dk are order-computable pseudovarieties. We also
S
S
have that K = k Kk , D = k Dk and LI is the join K ∨ D (i.e., LI is the least pseudovariety
containing both K and D). The following lemma summarizes well-known properties of these
pseudovarieties.
Lemma 2.1 Let V be one of the pseudovarieties K, D or LI. Then, ΩA V is isomorphic to
A+ and ΩA V \ ΩA V is an ideal of ΩA V consisting of the idempotent elements of ΩA V.
An implicit signature is a set of finitary implicit operations over finite semigroups containing the multiplication. The implicit signature κ = { . , ω−1 } is known as the canonical
signature. A highly computable signature is a recursively enumerable implicit signature consisting of computable operations. For an implicit signature σ, let TAσ denote the free σ-algebra
generated by A in the variety of σ-algebras defined by the identity x(yz) = (xy)z. The elements of TAσ will be called σ-terms. A σ-equation over A is a formal equality u = v with
u, v ∈ TAσ .
Every profinite semigroup has a natural structure of a σ-algebra, via the interpretation
of implicit operations as continuous operations on profinite semigroups, and a pseudovariety
of semigroups is also a pseudovariety of σ-semigroups. For a pseudovariety V, we denote by

Pointlike reducibility of pseudovarieties of the form V ∗ D

5

ΩσA V the free σ-semigroup generated by A in the variety of σ-semigroups generated by V,
which is a σ-subsemigroup of ΩA V. Elements of ΩσA V are called σ-words over V.
Consider the unique “evaluation” homomorphism of σ-semigroups εσA,V : TAσ → ΩσA V that
sends each letter a ∈ A to itself. The σ-word problem for V is the problem of deciding, for
any two given σ-terms u and v over an alphabet A, whether they represent the same σ-word
over V, that is, whether εσA,V u = εσA,V v. If so, we write V |= u = v. To simplify notation, we
will usually not distinguish a σ-term w ∈ TAσ from the corresponding σ-word εσA,S w ∈ ΩσA S.
For convenience, we allow the empty σ-term which is identified with the empty word.
For each pseudoword π ∈ ΩA S, we denote by ik π and tk π the shortest words (in Ak ) such
that Kk |= π = ik π and Dk |= π = tk π respectively. We define also ik w and tk w for a σ-term
w ∈ TAσ , via the identification of w with the corresponding σ-word εσA,S w ∈ ΩσA S.
Let Σ be a finite set of equations over a finite alphabet X. Let S be a finite A-generated
semigroup, δ : ΩA S → S be the continuous homomorphism respecting the choice of generators
and ϕ : X → S 1 be an evaluation mapping. We say that a mapping η : X → (ΩA S)1 is a Vsolution of Σ with respect to (ϕ, δ) if δη = ϕ and V |= ηu = ηv for all (u = v) ∈ Σ. Moreover,
given an implicit signature σ, if η is such that ηX ⊆ ΩσA S, then η is called a (V, σ)-solution.
The pseudovariety V is said to be σ-reducible relatively to an equation system Σ if the
existence of a V-solution of Σ with respect to a pair (ϕ, δ) entails the existence of a (V, σ)solution of Σ with respect to the same pair (ϕ, δ). The pseudovariety V is said to be σ-reducible
relatively to a class C of finite systems of equations if it is σ-reducible relatively to every system
of equations Σ ∈ C. We say that V is pointlike σ-reducible, if it is σ-reducible relatively to the
class of all systems of equations of the form x1 = x2 = · · · = xm , with m ≥ 2.

3

Pseudoidentities over V ∗ Dk

For an integer k ≥ 1, let Φk : A+ → (Ak+1 )∗ be the function that sends each word w ∈ A+ to
the sequence of factors of length k + 1 of w, in the order they occur in w. There is a unique
continuous extension ΩA S → (ΩAk+1 S)1 of Φk (see [3] and [1, Lemma 10.6.11]), also denoted
by Φk , which is a k-superposition homomorphism in the sense that
i) Φk w = 1 holds for every w ∈ Ak ;


ii) Φk (πρ) = Φk (π)Φk (tk π)ρ = Φk π(ik ρ) Φk (ρ) hold for every π, ρ ∈ ΩA S.

The following proposition ([1, Theorem 10.6.12]) gives a characterization of the pseudoidentities verified by a pseudovariety of the form V ∗ Dk .
Proposition 3.1 Let V be a pseudovariety of semigroups which is not locally trivial. Given
π, ρ ∈ ΩA S, V ∗ Dk |= π = ρ if and only if ik π = ik ρ, tk π = tk ρ and V |= Φk π = Φk ρ.
Throughout the paper, V denotes a pseudovariety of semigroups such that V * LI. A
S
consequence of Proposition 3.1 and of the fact that V ∗ D = ℓ V ∗ Dℓ , is that
V ∗ D |= π = ρ

⇔

LI |= π = ρ and V |= Φℓ π = Φℓ ρ for every ℓ ≥ 1.

(3.1)

6

J. C. Costa, C. Nogueira, M. L. Teixeira

Denote by A1k the set Ak ∪ {1} = {w ∈ A∗ : |w| ≤ k} of all words over A with length at
most k and let Bk = A1k × A. Notice that Bk = (ΩA Dk )1 × A and consider the action of ΩA Dk
on ΩBk V defined, for every w, w′ ∈ (ΩA Dk )1 and a ∈ A, by
w


(w′ , a) = tk (ww′ ), a ,

which determines a continuous endomorphism αw : ΩBk V → ΩBk V that maps each letter

(w′ , a) of Bk to the letter tk (ww′ ), a . This defines a semidirect product ΩBk V ∗ ΩA Dk
and there is a continuous embedding ι : ΩA (V ∗ Dk ) → ΩBk V ∗ ΩA Dk such that, for every

a ∈ A, ιa = (1, a), a [1, Theorem 10.2.3]. Composition of ι with the projection p1 on the
first component gives a continuous mapping βA : ΩA (V ∗ Dk ) → ΩBk V. That is to say that
the following diagram commutes, where p2 is the projection on the second component and
p = pA,V∗Dk ,Dk is the natural projection:
ΩA (V ∗ Dk )
βA



ΩBk V o

p

PPP
PPP ι
PPP
PPP
(
p1

/ ΩA Dk
O
p2

ΩBk V ∗ ΩA Dk

′ . As S ∗ D = S, it is a continuous
When V = S, the mapping βA will be denoted by βA
k
function ΩA S → ΩBk S. By [5, Lemma 3.1] the following equality holds
′
′
′
βA
(πρ) = βA
π · tk π βA
ρ

(3.2)

for all π, ρ ∈ ΩA S.

4

Implicit signatures

Following a concept introduced in [5], for a given implicit signature σ, we define a (σ, Dk )expressible signature as an implicit signature σ ′ such that
′

′ (Ωσ S) ⊆ Ωσ S for any alphabet A;
i) βA
A
Bk
′

ii) there is an algorithm that computes, from a given alphabet A and a given σ ′ -term z ∈ TAσ ,
′ z = t.
a σ-term t ∈ TBσk such that S |= βA
Denote by E σ the set of all (σ, Dk )-expressible signatures and notice that this set is non-empty
since it contains the trivial signature { . }. A signature σ ′ ∈ E σ is said to be σ-maximal if
′′
′
ΩσA S ⊆ ΩσA S for any signature σ ′′ ∈ E σ and any alphabet A. We notice that, if σ is highly
∗
computable, then E σ contains highly computable σ-maximal elements σ ∗ and ΩσA S ⊆ ΩσA S
for every alphabet A [5, Propositions 4.1 and 4.10].
Throughout, σ denotes a highly computable implicit signature and σ ∗ denotes a highly
computable σ-maximal signature verifying the following conditions:
(is.1) for every word u ∈ A+ , there is a computable σ-term eu ∈ TAσ such that S |= eu = uω ;

Pointlike reducibility of pseudovarieties of the form V ∗ D

7

∗

(is.2) for each integer k ≥ 1 and each σ ∗ -term w ∈ TAσ , it is possible to compute a σ ∗ -term
τw such that S |= w = (ik w)τw .
For each non-empty word u of length at most k, we fix a σ ∗ -term eu in the conditions above.
Note that ik eu = ik uω and tk eu = tk uω .
Let ν : ΩBk S → (ΩAk+1 S)1 be the continuous homomorphism such that, for (w, a) ∈ Bk ,
ν(w, a) = 1 if w ∈ Ak−1 and ν(w, a) = wa if w ∈ Ak . Hence, for every word w = a1 · · · an ∈ A+
with n > k,

′
′
′
νβA
w = ν βA
(a1 · · · ak ) · a1 ···ak βA
(ak+1 · · · an )


′
′
(ak+1 · · · an )
= ν βA
(a1 · · · ak ) ν a1 ···ak βA


= ν (1, a1 )(a1 , a2 ) · · · (a1 · · · ak−1 , ak ) ν (a1 · · · ak , ak+1 ) · · · (an−k · · · an−1 , an )

= ν (a1 · · · ak , ak+1 ) · · · (an−k · · · an−1 , an )
= Φk w.

′ , Φ and ν are continuous functions, we conclude that νβ ′ = Φ . That is, the following
As βA
k
k
A
diagram commutes:
ΩBk S

O

❑❑
❑❑ ν
❑❑
❑❑
❑%
Φk
/
ΩA S
(ΩAk+1 S)1

′
βA

For w = a1 · · · an ∈ A+ , Φk w is a finite word with length n − k if n > k and it is the empty
∗
word otherwise. For w ∈ TAσ \ A+ , by (3.2) and condition (is.2),
′
′
′
′
Φk w = νβA
w = ν(βA
ik w)ν(ik w βA
τw ) = ν(ik w βA
τw ).

Since σ ∗ is (σ, Dk )-expressible, it is possible to compute a σ-term on the alphabet Bk that
′ τ . Now, α
represents βA
w
ik w and ν restricted to Im αik w are continuous homomorphisms that
send letters to letters. So, it is possible to compute a σ-term on the alphabet Ak+1 that
′ τ ). This proves the following lemma.
represents ν(ik w βA
w
∗

Lemma 4.1 Given a σ ∗ -term w ∈ TAσ , there is a computable σ-term t ∈ TAσk+1 such that
S |= Φk w = t.
Let X be an alphabet and let Σ be a finite system of equations of the form x = x′ with
′ :Ω S→Ω
x, x′ ∈ X. Consider the mapping βX
X
X 1 ×X S. Then
k

′

Σ =

′
{βX
u

=

′
βX
v

: (u = v) ∈ Σ} = {(1, x) = (1, x′ ) : (x = x′ ) ∈ Σ}

is a set of equations over Xk1 × X of the same type of the equations of Σ and with the same
cardinal. Note also that the content of the equations of Σ′ is a subset of {(1, x) : x ∈ X}.
Σ ) of [5, Proposition 6.1] holds. In this
Consequently, if V is σ-reducible for Σ, condition (Dσ,σ
∗
′
context, we can identify Σ with Σ and the following statement is an instance of the above
mentioned proposition.

8

J. C. Costa, C. Nogueira, M. L. Teixeira

Proposition 4.2 For an alphabet X, let Σ be a finite system of equations of the form x = x′
with x, x′ ∈ X. If V is σ-reducible relatively to Σ, then V ∗ Dk is σ ∗ -reducible relatively to Σ.

Transforming V ∗ Dk -solutions into V ∗ D-solutions

5

The objective of this section is to build a function θk′ that will be used to convert (V ∗ Dk , σ ∗ )solutions of a pointlike system of equations into (V ∗ D, σ)-solutions of the same system.
Let S be a finite A-generated semigroup and denote by δ the extension of the corresponding
generating mapping A → S to an onto continuous homomorphism ΩA S → S. Let k be a
natural number such that |S| < k. For each word a1 · · · ak ∈ A+ of length k, we fix the
minimum j ∈ {2, . . . , k} such that δ(a1 · · · ai−1 ) = δ(a1 · · · aj ) for some i ∈ {2, . . . , j}, and

notice that δ(a1 · · · ai−1 ) = δ a1 · · · ai−1 (ai · · · aj )ω+1 . We fix next the minimum such i, so
that i and j are unique, well-determined and verify

δ(a1 · · · aj ) = δ a1 · · · aj (ai · · · aj )ω .

(5.1)

Consider now a finite word a1 · · · an with n ≥ k and note that it has r = n − k + 1
factors of length k. For each ℓ ∈ {1, . . . , r}, let uℓ = aiℓ · · · ajℓ where iℓ and jℓ are the
indices fixed above for the length k word aℓ · · · aℓ+k−1 . So δ(aℓ · · · ajℓ ) = δ(aℓ · · · ajℓ uωℓ ) and
ℓ < iℓ ≤ jℓ . We claim that jℓ ≤ jℓ+1 . Indeed, suppose that jℓ+1 < jℓ . By definition of iℓ+1
and jℓ+1 , δ(aℓ+1 · · · aiℓ+1 −1 ) = δ(aℓ+1 · · · ajℓ+1 ). Hence δ(aℓ · · · aiℓ+1 −1 ) = δ(aℓ · · · ajℓ+1 ). This
contradicts the minimality of jℓ and, so, the claim is true. Therefore,
δ(a1 · · · an ) = δ(a1 · · · aj1 uω1 aj1 +1 · · · aj2 uω2 aj2 +1 · · · ajr uωr ajr +1 · · · an )
= δ(a1 · · · aj1 eu1 aj1 +1 · · · aj2 eu2 aj2 +1 · · · ajr eur ajr +1 · · · an ).

(5.2)

With the above notation, consider the functions
A+ → ΩσA S

a1 · · · an
a1 · · · an 7→
a1 · · · aj1 eu1

λk :

and

A+ → (ΩσA S)1

1
a1 · · · an 7→
eur ajr +1 · · · an

if n < k
if n ≥ k

̺k :

if n < k
.
if n ≥ k

Note that for every w ∈ A+ , λk w = λk ik w and ̺k w = ̺k tk w.
Lemma 5.1 For each k ∈ N, there exist unique continuous functions ΩA S → ΩσA S and
ΩA S → (ΩσA S)1 extending λk and ̺k , respectively, that will also be denoted by λk and ̺k .
Proof.
Recall that ΩA S = A+ is a dense subset of ΩA S. Let (wm )m be a Cauchy sequence
in A+ . Since ΩA Kk (= ΩA Kk ) is a finite semigroup and pKk : ΩA S → ΩA Kk is a continuous

Pointlike reducibility of pseudovarieties of the form V ∗ D

9

homomorphism, there exists m0 ∈ N such that pKk wm = pKk wm0 for every m ≥ m0 . Hence,
ik wm = ik wm0 and λk wm = λk wm0 for every m ≥ m0 . As a consequence, λk has a unique
continuous extension λk : ΩA S → ΩσA S. Moreover, λk π = λk ik π for every π ∈ ΩA S. That ̺k
has a unique continuous extension, defined by ̺k π = ̺k tk π for every π ∈ ΩA S, can be shown
in a similar way using the pseudovariety Dk .
Let ψk : (ΩAk+1 S)1 → (ΩA S)1 be the unique continuous monoid homomorphism which
extends the mapping
Ak+1 → ΩσA S
a1 · · · ak+1 7→ eu1 aj1 +1 · · · aj2 eu2
and denote by θk the function θk = ψk Φk : ΩA S → (ΩA S)1 . This is a continuous ksuperposition homomorphism since it is the composition of a continuous k-superposition homomorphism with a continuous homomorphism. Finally, we define a mapping θk′ : ΩA S → ΩA S
by letting
θk′ π = (λk π)(θk π)(̺k π)
for every π ∈ ΩA S.
∗

Lemma 5.2 Let w ∈ ΩσA S. A representation of θk′ w as a σ-term may be computed from a
given representation of w as a σ ∗ -term.
Proof.
By (is.2) and Lemma 4.1, given a representation of w as a σ ∗ -term, one can calculate
a σ-term on the alphabet Ak+1 which represents Φk w. As ψk is a continuous homomorphism
that sends letters to σ-terms on A, it is then possible to compute a σ-term on A representing
θk w. On the other hand, λk w and ̺k w are respectively represented by σ-terms of the form veu
and eu v with v ∈ A∗ and u ∈ A+ , and it is easy to verify that these σ-terms can be computed
from (is.1) given ik w and tk w. The result follows from the definition of θk′ .
∗

An obvious consequence of the last lemma is that θk′ (ΩσA S) ⊆ ΩσA S. Let us now prove that
the mapping θk′ preserves the value over the fixed finite semigroup S.
Proposition 5.3 Let π ∈ ΩA S. Then δθk′ π = δπ.
Proof.
Since θk′ and δ are continuous functions and A+ is dense in ΩA S, it suffices to prove
the result for π = a1 · · · an ∈ A+ . For n ≤ k one has θk π = ψk 1 = 1, while for n > k one has,
with the notations of (5.2),
θk π = ψk (a1 · · · ak+1 , a2 · · · ak+2 , . . . , ar−1 · · · an )
= eu1 aj1 +1 · · · aj2 eu2 · eu2 aj2 +1 · · · aj3 eu3 · . . . · eur−1 ajr−1 +1 · · · ajr eur
= eu1 aj1 +1 · · · aj2 eu2 aj2 +1 · · · ajr−1 eur−1 ajr−1 +1 · · · ajr eur .

10

J. C. Costa, C. Nogueira, M. L. Teixeira

Thus, in case n < k, one deduces that θk′ π = λk π · θk π · ̺k π = π · 1 · 1 = π and, so, δθk′ π = δπ
holds certainly in this case. For n ≥ k, we have
θk′ π = λk (a1 · · · ak ) · θk π · ̺k (ar−1 · · · an )
= a1 · · · aj1 eu1 · θk π · eur ajr +1 · · · an
= a1 · · · aj1 eu1 aj1 +1 · · · aj2 eu2 aj2 +1 · · · ajr eur ajr +1 · · · an
and so, by (5.2), the equality δθk′ π = δπ holds also in this case. Therefore, the proposition is
true.
Let us now show the following fundamental property of the function θk′ .
∗

Proposition 5.4 Let π, ρ ∈ ΩσA S be such that V ∗ Dk |= π = ρ. Then V ∗ D |= θk′ π = θk′ ρ.
Proof.
By Proposition 3.1, ik π = ik ρ, tk π = tk ρ and V |= Φk π = Φk ρ. Therefore, if
either π ∈ Ak−1 , ρ ∈ Ak−1 or π, ρ ∈ Ak , then π and ρ are the same word and the result follows
∗
trivially. Thus, we may suppose that π, ρ ∈ ΩσA S\Ak−1 with at least one of π and ρ not in Ak .
Hence, there exist words v, y ∈ A∗ and u, x ∈ A+ such that λk π = λk ik π = λk ik ρ = λk ρ = veu
and ̺k π = ̺k tk π = ̺k tk ρ = ̺k ρ = ex y. Then, θk′ π = veu (θk π)ex y and θk′ ρ = veu (θk ρ)ex y and
to deduce V ∗ D |= θk′ π = θk′ ρ it suffices to prove that V ∗ D |= π ′ = ρ′ where
π ′ = eu (θk π)ex

and

ρ′ = eu (θk ρ)ex .

That LI |= π ′ = ρ′ holds is clear since S |= {eu = uω , ex = xω }. Therefore, by (3.1), to
conclude the proof of the proposition it remains to show that
∀ℓ ≥ 1, V |= Φℓ π ′ = Φℓ ρ′ .

(5.3)

In order to prove (5.3), consider the alphabet
e = {(u1 , v, u2 ) ∈ Ak × A1 × Ak : ∃w ∈ Ak+1 , θk w = eu veu }
A
k
1
2

and let ψek : (ΩAk+1 S)1 → (ΩAeS)1 be the continuous homomorphism extending the mapping
e
Ak+1 → A

a1 · · · ak+1 7→ (u1 , aj1 +1 · · · aj2 , u2 )
e ℓ : (Ω eS)1 → (ΩAℓ+1 S)1
with ψk (a1 · · · ak+1 ) = eu1 aj1 +1 · · · aj2 eu2 . Now, for each ℓ ≥ 1, let Φ
A
be the continuous homomorphism which extends the mapping
e → ΩAℓ+1 S
A


(u1 , v, u2 ) 7→ Φℓ eu1 veu2 (iℓ eu2 ) .

Pointlike reducibility of pseudovarieties of the form V ∗ D

11

The mappings involved are shown in the following (non-commutative) diagram:
1

4 (ΩA S) ▲▲
✐✐✐✐ r8
▲▲▲
θk ✐✐✐✐✐ rrrr
▲▲▲
✐
✐
r
✐
✐
r
r ψk
✐✐
✐
Φℓ ▲▲&
r
✐
✐
r
✐✐✐✐ /
(ΩAk+1 S)1
(ΩAℓ+1 S)1
ΩA S
▲▲▲
Φk
9
e ℓ rrrr
▲▲▲ψek
Φ
r
▲▲▲
rr
▲%
rrr

pV

/ (Ω ℓ+1 V)1
A

(ΩAeS)1

The next statement holds.
e ℓ ψek Φk w)(Φℓ ex ).
Claim 1 Let w ∈ {π, ρ}. Then Φℓ w′ = (Φ

Proof.
The proof for w = ρ being symmetric, we prove the result only for w = π. We
consider first the case in which π ∈ Ak . In this case π = ik π = tk π and Φk π = θk π = 1.
e ℓ ψek Φk π)(Φℓ ex ).
Hence u = x and so, as S |= ex = xω = ex ex , Φℓ π ′ = Φℓ (eu ex ) = Φℓ (ex ) = (Φ
+
Consider next π ∈ A \ Ak . Let r = |π| − k + 1 and notice that r ≥ 2. Then, |Φk π| = r − 1
and θk π is of the form θk π = eu1 v1 eu2 · · · vr−1 eur , with up ∈ Ak and vq ∈ A1k for all p and q.
Hence,
ψek Φk π = (u1 , v1 , u2 )(u2 , v2 , u3 ) · · · (ur−1 , vr−1 , ur ).
On the other hand, u1 = u and ur = x, so that π ′ = eu1 (θk π)eur = θk π. Thus, since Φℓ is an
ℓ-superposition homomorphism,



e ℓ ψek Φk π = Φℓ eu v1 eu (iℓ eu ) Φℓ eu v2 eu (iℓ eu ) · · · Φℓ eu vr−1 eur (iℓ eur )
Φ
r−1
2
3
3
1
2
2

= Φℓ eu1 v1 eu2 v2 · · · eur−1 vr−1 eur (iℓ eur )

= Φℓ (eu1 v1 eu2 v2 · · · eur−1 vr−1 eur )Φℓ (tℓ eur )(iℓ eur )

= (Φℓ π ′ )Φℓ (tℓ eur )(iℓ eur ) ,
whence, as π ′ is also equal to (θk π)eur ,
Φℓ π ′ = Φℓ (eu1 v1 eu2 v2 · · · eur−1 vr−1 eur eur )
= Φℓ (eu1 v1 eu2 v2 · · · eur−1 vr−1 eur )Φℓ (tℓ eur )eur

= (Φℓ π ′ )Φℓ (tℓ eur )(iℓ eur ) (Φℓ eur )
e ℓ ψek Φk π)(Φℓ ex ).
= (Φ



This concludes the proof of the claim in case π is a finite word.
Suppose at last that π ∈ ΩA S \ A+ and let (wm )m be a sequence in A+ converging to
π. Hence, since ik , tk : ΩA S → Ak are continuous homomorphisms, we may assume that
ik wm = ik π, tk wm = tk π and |wm | > k + 1 for every integer m ≥ 1. Hence, θk π and
θk wm are, respectively, of the forms θk π = eu γex and θk wm = eu γm ex for some γ, γm ∈ ΩA S.
′ = e (θ w )e = θ w . The claim is now an immediate
Hence π ′ = eu (θk π)ex = θk π and wm
u k m x
k m
e ℓ ψek Φk .
consequence of the previous case and of the continuity of the functions Φℓ θk and Φ

12

J. C. Costa, C. Nogueira, M. L. Teixeira

The validity of the proposition can now be easily achieved. Indeed, since V |= Φk π = Φk ρ
e ℓ ψek is a continuous homomorphism, one deduces from Claim 1 that V |=
by hypothesis and Φ
e ℓ ψek Φk π)(Φℓ ex ) = (Φ
e ℓ ψek Φk ρ)(Φℓ ex ) = Φℓ ρ′ . Since ℓ is arbitrary, this proves (5.3)
Φℓ π ′ = (Φ
and concludes the proof of the proposition.

6

Pointlike reducibility of V ∗ D

We are now able to show that the reducibility of the pointlike problem for V implies the
reducibility of the pointlike problem for V ∗ D. Recall that σ is a fixed highly computable
signature and σ ∗ is a highly computable σ-maximal signature verifying (is.1) and (is.2).
Theorem 6.1 Let X be an alphabet and Σ be a finite set of equations of the form x = x′ with
x, x′ ∈ X. If V is σ-reducible relatively to Σ, then V ∗ D is σ-reducible relatively to Σ.
Proof.
Let S be a finite A-generated semigroup, δ : ΩA S → S be the continuous homomorphism that extends the generating mapping of S and ϕ : X → S 1 be a function. Suppose
that η : X → ΩA S is a V ∗ D-solution of Σ with respect to the pair (ϕ, δ). Hence, for every
integer k ≥ 1, as V ∗ Dk is a subpseudovariety of V ∗ D, η is also a V ∗ Dk -solution of Σ with
respect to the same pair (ϕ, δ).
Let us assume that V is σ-reducible relatively to Σ. Then, by Proposition 4.2, V ∗ Dk is
relatively to Σ for every k ≥ 1, whence there is a (V ∗ Dk , σ ∗ )-solution ηk of Σ
with respect to the pair (ϕ, δ). Fix an integer k > |S|. Hence, by Propositions 5.3 and 5.4
and Lemma 5.2, θk′ ηk is a (V ∗ D, σ)-solution of Σ with respect to the pair (ϕ, δ).
σ ∗ -reducible

Corollary 6.2 If V is pointlike σ-reducible, then V ∗ D is pointlike σ-reducible.
The canonical signature κ is an example of a highly computable κ-maximal signature [5]
that verifies (is.1) and (is.2). Hence, the following is a particular case of Corollary 6.2.
Corollary 6.3 If V is pointlike κ-reducible, then V ∗ D is pointlike κ-reducible.
This result applies, for instance, to the pseudovarieties Sl, G, J and R.

Acknowledgments
This work was supported by the European Regional Development Fund, through the programme COMPETE, and by the Portuguese Government through FCT – Fundação para a
Ciência e a Tecnologia, under the project PEst-C/MAT/UI0013/2014.

Pointlike reducibility of pseudovarieties of the form V ∗ D

13

References
[1] J. Almeida, Finite Semigroups and Universal Algebra, (World Scientific, Singapore, 1995).
English translation.
[2] J. Almeida, Finite semigroups: an introduction to a unified theory of pseudovarieties,
in Semigroups, Algorithms, Automata and Languages (Coimbra, 2001), World Scientific,
2002, pp. 3–64.
[3] J. Almeida and A. Azevedo, On regular implicit operations, Portugaliæ Mathematica 50
(1993), 35–61.
[4] J. Almeida, A. Azevedo and M. L. Teixeira, On finitely based pseudovarieties of the forms
V ∗ D and V ∗ Dn , J. Pure Appl. Algebra 146 (2000), 1–15.
[5] J. Almeida, J. C. Costa and M. L. Teixeira, Semidirect product with an order-computable
pseudovariety and tameness, Semigroup Forum 81 (2010), 26–50.
[6] J. Almeida, J. C. Costa and M. Zeitoun, Tameness of pseudovariety joins involving R,
Monatsh. Math. 146 (2005), 89–111.
[7] J. Almeida, J. C. Costa and M. Zeitoun, Reducibility of pointlike problems, Semigroup
Forum, to appear.
[8] J. Almeida and B. Steinberg, Syntactic and global semigroup theory: a synthesis approach, in Algorithmic Problems in Groups and Semigroups (Lincoln, NE, 1998), Trends
Math. (Birkhäuser Boston, Boston, MA, 2000), pp. 1–23.
[9] J. Almeida and M. Zeitoun, Tameness of some locally trivial pseudovarieties, Comm.
Algebra 31 (2003), 61–77.
[10] C. Ash, Inevitable graphs: a proof of the type II conjecture and some related decision
procedures, Int. J. Algebra Comput. 1 (1991), 127–146.
[11] K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc.
Amer. Math. Soc. 131 (2003), 2693–2703.
[12] J. C. Costa and M. L. Teixeira, Tameness of the pseudovariety LSl, Int. J. Algebra
Comput. 14 (2004), 627–654.
[13] S. Eilenberg, Automata, Languages and Machines, vol. B, (Academic Press, New York,
1976).
[14] 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.

14

J. C. Costa, C. Nogueira, M. L. Teixeira

[15] D. Perrin, Finite automata, in Handbook of Theoretical Computer Science, vol. B: Formal
Models and Semantics, (Elsevier, 1990), pp. 1–57.
[16] J.-É. Pin, Syntactic semigroups, in Handbook of Formal Languages, vol. 1, (Springer,
1997), pp. 679–746.
[17] J. Rhodes, Undecidability, automata and pseudovarieties of finite semigroups, Int. J.
Algebra Comput. 9 (1999), 455–473.
[18] J. Rhodes and B. Steinberg, The q-theory of Finite Semigroups: A New Approach,
(Springer Monographs in Mathematics, 2009).
[19] B. Steinberg, A delay theorem for pointlikes, Semigroup Forum 63 (2001), 281–304.
[20] H. Straubing, Finite semigroup varieties of the form V ∗ D, J. Pure Appl. Algebra 36
(1985), 53–94.
[21] D. Thérien and A. Weiss, Graph congruences and wreath products, J. Pure Appl. Algebra
36 (1985), 205–215.
[22] B. Tilson, Categories as algebra: an essential ingredient in the theory of monoids, J. Pure
Appl. Algebra 48 (1987), 83–198.
[23] W. Thomas, Languages, automata, and logic, in Handbook of Formal Languages, vol. 3:
Beyond Words, (Springer, Berlin, 1997), pp. 389–455.

