arXiv:1708.08118v1 [] 27 Aug 2017

MERGE DECOMPOSITIONS, TWO-SIDED KROHN-RHODES, AND
APERIODIC POINTLIKES
SAMUEL J. V. GOOL AND BENJAMIN STEINBERG
Abstract. This paper provides short proofs of two fundamental theorems of finite semigroup theory whose previous proofs were significantly longer, namely the two-sided KrohnRhodes decomposition theorem and Henckell’s aperiodic pointlike theorem, using a new algebraic technique that we call the merge decomposition. A prototypical application of this
technique decomposes a semigroup T into a two-sided semidirect product whose components
are built from two subsemigroups T1 , T2 , which together generate T , and the subsemigroup
generated by their setwise product T1 T2 . In this sense we decompose T by merging the
subsemigroups T1 and T2 . More generally, our technique merges semigroup homomorphisms
from free semigroups.

Introduction
Eilenberg’s variety theorem [3] provides a dictionary between formal language theory and finite
semigroup theory. In particular, membership problems in certain Boolean algebras of regular
languages (languages accepted by finite automata) are equivalent to membership problems
in varieties of finite semigroups. Other natural problems in language theory transform into
questions about pointlikes with respect to a variety of finite semigroups, a notion introduced by
Henckell and Rhodes [4]. An important problem in language theory is the separation problem:
given disjoint regular languages, determine whether they can be separated by a language from
a given variety of regular languages. The separation problem is equivalent to decidability of
pointlike pairs [1], which is strictly stronger than the membership problem [10, 2]. Decidability
of pointlikes can be used to obtain decidability of membership problems of related varieties.
For instance, the second author showed, using the decidability of aperiodic pointlikes and
Zelmanov’s solution to the restricted Burnside problem, that the join of the variety of aperiodic
semigroups with any variety of finite groups of bounded exponent has decidable membership
problem, answering a question of Rhodes and Volkov [13].
The first decidability result on pointlikes was Henckell’s theorem on the decidability of aperiodic pointlikes [4], which for a long time was considered one of the most difficult results in the
subject. Henckell not only provided a decidability algorithm: he also gave an elegant structural description of the aperiodic pointlike sets that we call Henckell’s formula. Henckell’s
original proof idea is a variation on the holonomy proof [5] of the Krohn-Rhodes theorem [7]
for directly decomposing semigroups into wreath products. The difficult part of Henckell’s
proof is to prove that a certain semigroup is aperiodic, which he does by wreath product
embeddings. In [6], Henckell, Rhodes and the second author provided a direct proof that
Henckell’s semigroup is aperiodic, leading to a simpler and shorter proof of his main theorem.
They also extended the theorem beyond aperiodic pointlikes to the variety of semigroups
Date: August 29, 2017.
The first-named author was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant #655941; the second-named author was supported by United
States - Israel Binational Science Foundation #2012080 and NSA MSP #H98230-16-1-0047.
1

2

SAMUEL J. V. GOOL AND BENJAMIN STEINBERG

whose subgroups have prime divisors belonging to a fixed set π of primes (the restriction of
this proof to the aperiodic case can be found in [11, Ch. 4]). Although simpler than the
original proof of Henckell [4], the proof in [6] is still non-trivial.
Recently, Place and Zeitoun [9] gave a new proof of the decidability of aperiodic pointlikes,
which, unlike the previous proofs, is inductive. They use a language theoretic reformulation of
the problem of computing pointlike sets and the McNaughton-Schützenberger theorem that
the aperiodic languages are precisely the first order definable languages [14]. The PlaceZeitoun approach follows the inductive proof scheme of the Krohn-Rhodes theorem (the socalled ‘V ∪ T ’ argument [8, 11]) later used by Wilke in the logic context [15], but done in the
power set of the semigroup.
This paper introduces a new algebraic tool, that we call the merge decomposition, in Section 2.
In Section 3, we use this tool to give a short proof of the inductive step of the two-sided
Krohn-Rhodes decomposition theorem (cf. [11, Ch. 5]). Then, in Section 4, we use the merge
decomposition in the inductive step of the Place-Zeitoun inductive scheme to give a short
algebraic proof of Henckell’s formula for the aperiodic pointlikes. We feel that our approach
has several advantages over previous approaches [4, 6, 9]. First of all, it leads to a significantly
shorter proof than the previous ones. Secondly, we obtain the best known bound on the length
of a two-sided Krohn-Rhodes decomposition of the aperiodic semigroup witnessing pointlikes
(or, equivalently, quantifier-depth of the first order formula giving separation).
An advantage of our approach is that it is potentially extendable beyond the realm of first
order logic on words. For instance, decidability of pointlikes for some larger varieties than
aperiodics is obtained in [6]. We leave this to future work.
1. Preliminaries
We assume familiarity with notions from the theory of semigroups, in particular, relational
morphisms and divisions, the wreath product (denoted ≀), and the two-sided semidirect product of semigroups (denoted ⊲⊳) and of varieties of finite semigroups (denoted ∗∗); see, e.g., [11,
Ch. 1]. Throughout the paper, we call ‘variety’ what is called ‘pseudovariety’ in [11].
Augmented semigroups. Let T be a finite semigroup. Let T I be the monoid obtained by
adjoining a new identity, I, to T and T 0 the semigroup obtained by adjoining a new zero to
T . We denote by SL the variety of finite semilattices and by U1 the two-element semilattice.
Fact 1.1. If a variety V contains T and SL, then T 0 ∈ V. If a variety V contains T , SL,
and is generated by monoids, then T I ∈ V.
Proof. The first statement is true because T 0 is a homomorphic image of T × U1 [3, Ex. I.9.2].
For the second statement, we distinguish two cases. If T is a monoid, then T I embeds in
T × U1 , where U1 denotes the two-element semilattice [3, Ex. I.9.1]. If T is not a monoid,
then T divides some monoid M ∈ V, and since T is not a monoid, it follows that T I divides
the same monoid M .

The semigroup T acts faithfully on T I by multiplication on the right, and thus T embeds into
the semigroup of total functions on T I ; we identify every element t ∈ T with the corresponding
right multiplication map. Further, for every t ∈ T I , we denote by t♯ the function with constant
value t. We define T ♯ := T ∪{t♯ : t ∈ T I }, the semigroup consisting of the right multiplication
maps and the constant maps. Thus, T ♯ naturally acts on T on the right.1 Dually, T ♭ denotes
1Note that our definition of T ♯ for a semigroup T deviates slightly from the definition of M ♯ for a monoid M
in [11, Subsec. 4.1.2].

MERGE DECOMPOSITIONS, TWO-SIDED KROHN-RHODES, AND APERIODIC POINTLIKES

3

the semigroup consisting of left multiplication maps for every t ∈ T and constant maps t♭ for
every t ∈ T I . Note that T ♭ = ((T op )♯ )op , and T ♭ acts on T on the left.
Fact 1.2. For any finite semigroup T , let Te denote the monoid obtained from T by adjoining
an identity and a zero and let M be any monoid with |M | > |T |. Then T ♭ embeds in M ≀ Te.

Proof. Fix a bijection t 7→ mt between T and a subset of M \ {1M }. We define a function
e
i : T ♭ → M ≀ Te. For every t ∈ T , define i(t) := (c1 , t), where c1 ∈ M T denotes the function
e
with constant value 1M , the identity of M , and i(t♭ ) := (ft , 0), where ft ∈ M T denotes the
function defined by ft (0) := 1M and ft (t′ ) := mt′ t for all t′ ∈ T I . It is straightforward to
verify that i is an injective homomorphism.

Triple product. Let (S, +) be a (not necessarily commutative) semigroup equipped with two
actions on it, a left action of a semigroup (SL , ·) and a right action of a semigroup (SR , ·),
which commute. The triple product 2 T = (SR , S, SL ) is the semigroup of triples (sR , s, sL ),
with multiplication defined by (sR , s, sL ) · (s′R , s′ , s′L ) := (sR s′R , ss′R + sL s′ , sL s′L ).
Fact 1.3. If S ∈ V and SL , SR ∈ W, then (SR , S, SL ) ∈ V ∗∗ W.
Proof. Define an action of SL × SR on S by hsL , sR is := sL s and shsL , sR i := ssR . Then T is
isomorphic to the two-sided semidirect product S ⊲⊳ (SL × SR ). (Cf., e.g., [3, Sec. V.9].) 
2. The merge decomposition
Throughout this section, we fix:
• a finite alphabet A and two disjoint subalphabets A1 , A2 such that A = A1 ∪ A2 ;
+
• two homomorphisms ψ1 : A+
1 → T1 and ψ2 : A2 → T2 , with T1 and T2 finite;
+
• a homomorphism χ : (T1 × T2 ) → T0 .
+
For any w1 ∈ A+
1 , w2 ∈ A2 , define µ(w1 w2 ) := (ψ1 (w1 ), ψ2 (w2 )) ∈ T1 × T2 . Since the
+
+ + +
subsemigroup (A1 A2 ) of A+ is freely generated by the infinite set of generators A+
1 A2 ,
+ + +
the function µ extends uniquely to a homomorphism µ : (A1 A2 ) → (T1 × T2 )+ . We define
+ +
→ T0 to be the composition χ ◦ µ. For i = 0, 1, 2, we denote the external
ψ0 : (A+
1 A2 )
identity of TiI by Ii , and we also denote by ψi the homomorphism from the corresponding free
monoid to the finite monoid TiI ; i.e., ψi (ε) := Ii .
+ ∗
∗
For any word w in A+ , uniquely write w = v2 uv1 , with v2 ∈ A∗2 , u ∈ (A+
1 A2 ) , and v1 ∈ A1 ,
I
I
+
I
and define τ (w) := (ψ2 (v2 ), ψ0 (u), ψ1 (v1 )). The function τ : A → T2 × T0 × T1 is not a
homomorphism in general. The aim in this section is to show that the kernel of τ can be
refined to a semigroup congruence of finite index in a well-controlled variety.
To this end, we will define a semigroup TM and a homomorphism ψM : A+ → TM . Let
I
I
S := (T0I )T1 ×T2 , with the pointwise product of T0I , written additively. We define a left action
of T1♯ and a right action of T2♭ on S. For s ∈ S, sL ∈ T1♯ and sR ∈ T2♭ , let sL ssR ∈ S be defined
by [sL ssR ](t1 , t2 ) := s(t1 sL , sR t2 ) for every (t1 , t2 ) ∈ T1I × T2I . Let TM := (T2♭ , S, T1♯ ) be the
triple product; we call TM the merge semigroup associated to ψ1 , ψ2 and χ.
Fact 2.1. Let V be a variety, and W a variety generated by monoids and containing SL.
I
I
If T0 ∈ V , T1 , T2 ∈ W, and TM is any triple product of T2♭ , (T0I )T1 ×T2 , and T1♯ , then
TM ∈ V ∗∗ (SL ∗∗ W).
2We follow the notation of [3, Sec V.9]; note the positions of the semigroups acting on the left and on the right.

Also note that the multiplication
 can be
 viewed as matrix multiplication, if we represent an element (sR , s, sL )
by the lower triangular matrix ssR s0L .

4

SAMUEL J. V. GOOL AND BENJAMIN STEINBERG

Proof. Applying Fact 1.2 with M a semilattice (e.g., a chain) with |T2 | + 1 elements and using
f
T2 ∈ W by Fact 1.1 yields T2♭ ∈ SL ∗∗ W. Similarly, T1♯ ∈ SL ∗∗ W. Fact 1.3 gives the
result.

For any w1 ∈ A+
1 , we define an element sw1 ∈ S by sw1 (t1 , I2 ) := I0 and sw1 (t1 , t2 ) :=
χ(t1 ψ1 (w1 ), t2 ), for all t1 ∈ T1I and t2 ∈ T2 . Now let ψM : A+ → TM be the unique homomorphism defined by
ψM (a1 ) := (I2♭ , sa1 , ψ1 (a1 )) for a1 ∈ A1 ,

ψM (a2 ) := (ψ2 (a2 ), i0 , I1♯ ) for a2 ∈ A2 ,

where i0 denotes the identity of S, i.e., the function with constant value I0 . We call the
homomorphism ψM : A+ → TM the merge decomposition of A+ along χ, ψ1 and ψ2 .
The crucial property of the merge decomposition is the following.
Proposition 2.2. There exists a function f : TM → T2I × T0I × T1I such that f ◦ ψM = τ .
Proof. For any (t2 , s, t1 ) ∈ TM , define f (t2 , s, t1 ) := (t2 I2 , s(I1 , I2 ), I1 t1 ). We show f ◦ψM = τ .
♭
We first prove, for all w1 ∈ A+
1 , ψM (w1 ) = (I2 , sw1 , ψ1 (w1 )). By induction, assume that this
+
holds for all shorter words in A1 . Then, writing w1 = a1 w1′ , the left and right coordinates are
clearly as stated, and the middle coordinate of ψM (w1 ) = ψM (a1 )ψM (w1′ ) is sa1 I2♭ +ψ1 (a1 )sw1′ .
From the definition of the right action and of sa1 we get that sa1 I2♭ = i0 . From the definition
of the left action and of sw1′ and sw1 , we get that ψ1 (a1 )sw1′ = sw1 . For w2 ∈ A+
2 , we easily
obtain ψM (w2 ) = (ψ2 (w2 ), i0 , I1♯ ), since sL i0 sR = i0 for all sL , sR , because i0 is a constant map.
♯
+
♭
Multiplying these two results, for any w1 ∈ A+
1 and w2 ∈ A2 , ψM (w1 w2 ) = (I2 , sw1 w2 , I1 ),
where sw1w2 (I1 , I2 ) = sw1 (I1 , ψ2 (w2 )) = χ(ψ1 (w1 ), ψ2 (w2 )) = ψ0 (w1 w2 ).
+ +
We next prove, by induction on the length of u ∈ (A+
1 A2 ) as a word in the free semigroup
♯
+
♭
generated by A+
1 A2 , that ψM (u) = (I2 , su , I1 ), where su (I1 , I2 ) = ψ0 (u). We have already
+
+ + +
′
′
established the base case. If u = (w1 w2 )u for some w1 ∈ A+
1 and w2 ∈ A2 with u ∈ (A1 A2 ) ,
then, for the middle coordinate su of ψM (u) = ψM (w1 w2 )ψM (u′ ), we have
su (I1 , I2 ) = [sw1 w2 I2♭ + I1♯ su′ ](I1 , I2 ) = ψ0 (w1 w2 ) · ψ0 (u′ ) = ψ0 (u).
+ +
Finally, to prove that f ◦ ψM = τ , let w ∈ A+ . Suppose that w = v2 uv1 with u ∈ (A+
1 A2 ) ,
+
+
v1 ∈ A1 and v2 ∈ A2 . Then, using our previous calculations, we get

ψM (v2 uv1 ) = (ψ2 (v2 ), i0 , I1♯ ) · (I2♭ , su , I1♯ ) · (I2♭ , sv1 , ψ1 (v1 )) = (ψ2 (v2 )♭ , s, ψ1 (v1 )♯ ),
where
s(I1 , I2 ) =




i0 I2♭ + I1♯ su I2♭ + I1♯ sv1 (I1 , I2 ) = I0 · su (I1 , I2 ) · I0 = ψ0 (u).

Thus, in this case, f (ψM (w)) = τ (w). If one or more of the factors in the factorization
w = v2 uv1 are empty, then the proof is similar but simpler.

We end with a prototypical application of the technique, to be used in the next section.
Corollary 2.3. Let S be a finite semigroup and let T1 , T2 be subsemigroups of S such that
T1 ∪ T2 generates S. Denote by T0 := hT1 T2 i, the subsemigroup generated by T1 T2 . Then the
I
I
semigroup S divides a triple product of T2♭ , (T0I )T1 ×T2 , and T1♯ .
Proof. Let Ai := Ti × {i} for i = 1, 2 and A := A1 ∪ A2 . Denote by ψ : A+ ։ S the surjective
homomorphism defined on generators (ti , i) ∈ A by ψ(ti , i) := ti . For i = 1, 2, let ψi be
+
the restriction of ψ to A+
i , and let χ : (T1 × T2 ) → T0 be the homomorphism defined by
χ(t1 , t2 ) := t1 t2 for (t1 , t2 ) ∈ T1 × T2 . Note that ψ0 , as defined above, in this case turns

MERGE DECOMPOSITIONS, TWO-SIDED KROHN-RHODES, AND APERIODIC POINTLIKES

5

+ +
I
I
I
I
out to be the restriction of ψ to (A+
1 A2 ) . Hence, writing m : T2 × T0 × T1 → T for the
multiplication map m(t2 , t0 , t1 ) := t2 t0 t1 , we have ψ = m ◦ τ . Let ψM : A+ → TM be the
merge decomposition along χ, ψ1 , and ψ2 . By Proposition 2.2, pick f : TM → T2I × T0I × T1I
such that τ = f ◦ ψM . Then ψ = m ◦ f ◦ ψM , so S divides TM since ψ is surjective.


3. Two-sided Krohn-Rhodes theorem
In this section, we apply the merge decomposition technique of Section 2 to give a short proof
of the crucial step in the two-sided Krohn-Rhodes theorem.
For any finite semigroup S, define VS to be the smallest variety which is closed under twosided semidirect products, and which contains SL and all simple groups that divide S.
Theorem 3.1 (Two-sided Krohn-Rhodes). Let S be a finite semigroup. Then S ∈ VS .
Proof. By induction on |S|.
Case 1. S is a group. Any finite group embeds in an iterated wreath product of its simple
group divisors, cf., e.g., [11, Cor. 4.1.6].
Case 2. S is cyclic. Any finite cyclic semigroup divides an iterated wreath product of a subgroup and copies of U1 , cf., e.g., [11, Cor. 4.1.28].
Case 3. S is not a group and S is not cyclic. Let A be a minimal generating set for S and
note that |A| ≥ 2. Since S is not a group, without loss of generality, S is not right simple
(cf., e.g., [11, Lem. A.3.3]). Therefore, there exists a ∈ A such that aS ( S. Let A1 := {a},
A2 := A \ A1 , Ti := hAi i for i = 1, 2, and T0 := hT1 T2 i. By minimality of A, T1 and T2 are
strictly contained in S. By the induction hypothesis, Ti ∈ VTi , which is contained in VS ,
since any simple group dividing Ti also divides S. Moreover, T0 ⊆ aS, so T0 is also strictly
contained in S. By the induction hypothesis again, T0 ∈ VT0 ⊆ VS . Since T1 ∪ T2 generates
I
I
S, by Corollary 2.3, S divides a triple product of T2♭ , (T0I )T1 ×T2 , and T1♯ . Hence, by Fact 2.1,
S ∈ VS ∗∗ (VS ∗∗ VS ) = VS .

4. Henckell’s theorem on aperiodic pointlikes
Recall that any element s in a finite semigroup S has a unique idempotent power, sω . A
semigroup S is called aperiodic if every subgroup of S is trivial, or, equivalently, sω s = sω for
every s ∈ S. For k ≥ 1, define SLk+1 := SL ∗∗ SLk . A semigroup S is aperiodic if, and only
if, S ∈ SLk for some k; indeed, the necessity follows from Theorem 3.1.3
Fact 4.1. For any m, n ≥ 1, SLm ∗∗ SLn ⊆ SLm+n .
Proof. By induction on m. The case m = 1 is true by definition. By the lax associativity of
double semidirect product [11, Cor. 2.6.26], (SL ∗∗ SLm−1 ) ∗∗ SLn ⊆ SL ∗∗ (SLm−1 ∗∗ SLn ).
By the induction hypothesis, SL ∗∗ (SLm−1 ∗∗ SLn ) ⊆ SL ∗∗ SLm+n−1 = SLm+n .

Let V be a variety. A subset X of a finite semigroup S is called V-pointlike if, for any
relational morphism ρ : S →
7 T with T ∈ V, X ⊆ ρ−1 (t) for some t ∈ T . Any singleton set
is V-pointlike, and the collection of V-pointlike subsets of a semigroup S forms a downward
closed subsemigroup, PLV (S), of the power semigroup 2S , partially ordered by inclusion, and
with multiplication of subsets of S.
The following observation is specific to the variety
A of aperiodic semigroups: if X is an AS
pointlike set in S, then so is the set X ω+∗ := n≥0 X ω X n . Indeed, for any ρ : S →
7 T with T
3A finite semigroup S lies in SLk if, and only if, every language recognized by S can be defined by a first-order
sentence of quantifier depth ≤ k; this result is contained in [14, Ch. VI], and relates our work in Section 4 to
the logical approach of [9].

6

SAMUEL J. V. GOOL AND BENJAMIN STEINBERG

aperiodic, X ⊆ ρ−1 (t) for some t ∈ T , which gives X m ⊆ ρ−1 (tm ) for all m ≥ 1. Aperiodicity
of T then yields X ω X n ⊆ ρ−1 (tω ) for all n ≥ 0.
We will call a subset U of 2S saturated, if it is a subsemigroup that is closed downward in the
inclusion order and closed under the operation X 7→ X ω+∗ . Clearly, any subset U of 2S is
contained in a smallest saturated set, which we call its saturation, and denote by Sat(U ).
We will need the following lemma, which was essentially already in [4]; see also [6].
S
Lemma 4.2. Let G be a subgroup of 2S . Then G ∈ Sat(G).
Proof. Let C1 , . . . , Ck be anSexhaustive
S list of the cyclic subgroups of G. Note that, for any
generator X of Ci , X ω+∗ = Ci , so Ci ∈ Sat(G) forS
every i.SAlso noteSthat G = C1 · · · Ck .
Therefore, since multiplication distributes over union, G = ( C1 ) · · · ( Ck ) ∈ Sat(G). 
We will use the merge decomposition (Section 2) to give a short proof of the following theorem.
Theorem 4.3 (cf. [4, 6, 9]). Let S be a semigroup. The set PLA (S) is the saturation of the
set of singletons in 2S . Moreover, if A is a generating set for S, then PLA (S) = PLSLk (S),
|S|
where k = (|A| − 1)2( 2 ) + 2|A| − 1.
Proof. Throughout the proof, for any finite alphabet A, semigroup S, and homomorphism
S
(|S2ϕ |)
+ 2|Sϕ | − 1.
ϕ : A+ → 2S , define Uϕ := im(ϕ), Sϕ := Uϕ , and k(ϕ) := (|ϕ(A)| − 1)2

Claim. For any homomorphism ϕ : A+ → 2S \{∅}, there exists a homomorphism ψ : A+ → T
S
with T ∈ SLk(ϕ) and ϕ(ψ −1 t) ∈ Sat(Uϕ ) for every t ∈ T .

Proof of Claim. The construction of ψ : A+ → T with T ∈ SLk(ϕ) is by induction on the
parameter (|Sϕ |, |ϕ(A)|) in N2 , ordered lexicographically.
Case 1. For every a ∈ A, ϕ(a)Sϕ = Sϕ = Sϕ ϕ(a).
Let e = ϕ(w) be an idempotent in the minimal
S ideal of Uϕ . Then G := eUϕ e is a subgroup of
Uϕ , see, e.g., [11, App. A]. By Lemma 4.2, G lies in Sat(eUϕ e), and hence also in Sat(Uϕ ),
since eUϕ e ⊆ Uϕ . Using the assumption in this case and the fact that multiplication distributes
over union, we have
[ 
[
G.
Sϕ = ϕ(w)Sϕ ϕ(w) = e
Uϕ e =
Thus, Sϕ lies in Sat(Uϕ ), and we choose ψ to be the trivial homomorphism A+ → {1} ∈ SL.
Case 2. |ϕ(A)| = 1.
Denote the unique element of ϕ(A) by X. Since Uϕ is a finite cyclic semigroup, pick m ≤ |Uϕ |
such that X m is idempotent, i.e., X m = X ω . Let T := hx | xm = xm+1 i, the finite aperiodic
cyclic semigroup of order m, and let ψ : A+ → T be the homomorphism defined by a 7→ x for
every letter a ∈ A. Note that T ∈ SLm [11, Lem. 4.1.27], and, since Uϕ ⊆ 2Sϕ \ {∅}, we have
S
m ≤ |Uϕ | ≤ 2|Sϕ | −1 = k(ϕ). From
the
definitions,
note
that,
for
1
≤
i
<
m,
ϕ(ψ −1 xi ) = X i ,
S
−1
i
ω+∗
which lies in Uϕ , and for i ≥ m, ϕ(ψ x ) = X
, which lies in Sat(Uϕ ).

Case 3. |ϕ(A)| ≥ 2, and there is a0 ∈ A such that ϕ(a0 )Sϕ ( Sϕ or Sϕ ϕ(a0 ) ( Sϕ .

Without loss of generality, we may assume ϕ(a0 )Sϕ ( Sϕ . Let A1 := {a ∈ A | ϕ(a) = ϕ(a0 )},
and A2 := A \ A1 . Note that, since |ϕ(A)| ≥ 2, ϕ(A1 ) and ϕ(A2 ) are non-empty proper
+
subsets of ϕ(A). For i = 1, 2, denote by ϕi the restriction of ϕ to A+
i , and pick ψi : Ai → Ti
S
S
with Ti ∈ SLk(ϕi ) and ϕ(ψi−1 t) = ϕi (ψi−1 t) ∈ Sat(Uϕi ) ⊆ Sat(Uϕ ), for all t ∈ Ti . Without
loss of generality, we may assume the ψi are surjective.

MERGE DECOMPOSITIONS, TWO-SIDED KROHN-RHODES, AND APERIODIC POINTLIKES

7

Let ϕ0 : (T1 ×ST2 )+ → 2S \ {∅} be the unique homomorphism defined, for (t1 , t2 ) ∈ T1 × T2 , by
ϕ0 (t1 , t2 ) := ϕ(ψ1−1 t1 · ψ2−1 t2 ). Note that Sϕ0 ⊆ ϕ(a0 )Sϕ , since any w ∈ ψ1−1 t1 · ψ2−1 t2 starts
with a letter from the subalphabet A1 . Since ϕ(a0 )Sϕ ( Sϕ by assumption, |Sϕ0 | < |Sϕ |,
so the induction hypothesis applies to ϕ0 : pick a homomorphism χ : (T1 × T2 )+ → T0 with
S
T0 ∈ SLk(ϕ0 ) such that ϕ0 (χ−1 (t)) ∈ Sat(Uϕ0 ) ⊆ Sat(Uϕ ), for every t ∈ T0 .
+ +
Define µ : (A+
→ (T1 × T2 )+ and ψ0 := χ ◦ µ, as in Section 2. Note that, for any
1 A2 )
+
+
w1 ∈ A1 , w2 ∈ A2 , we have ϕ(w1 w2 ) ⊆ ϕ0 (µ(w1 w2 )), and, hence, ϕ(w) ⊆ ϕ0 (µ(w)) for all
S
S
w ∈ (A+
A+ )+ . Therefore, by the definition of ψ0 , ϕ(ψ0−1 t) ⊆ ϕ0 (χ−1 t) for all t ∈ T0 , so
S 1 2−1
also ϕ(ψ0 t) ∈ Sat(Uϕ ). Applying the construction of Section 2, let ψM : A+ → TM be the
merge homomorphism, and pick f : TM → T2I × T0I × T1I such that f ◦ ψM = τ . Let t ∈ TM ,
and write f (t) = (t2 , t0 , t1 ) ∈ T2I × T0I × T1I . If (t2 , t0 , t1 ) ∈ T2 × T0 × T1 , then
[
[
[
[
[
−1
t) ⊆
ϕ(τ −1 (t2 , t0 , t1 )) =
ϕ(ψ2−1 t2 ) ·
ϕ(ψ0−1 t0 ) ·
ϕ(ψ1−1 t1 ) ∈ Sat(Uϕ ),
ϕ(ψM
and, if tS
i = Ii for one or more i ∈ {0, 1, 2}, a similar inclusion holds, omitting the corresponding
factors ϕ(ψi−1 ti ) from the final product.
Let us write m := |Sϕ |. Note that, since Sϕ0 is strictly contained in Sϕ and ϕ0 (T1 × T2 ) is
contained in 2Sϕ0 \ {∅}, we have
m
m−1
m
m−1
k(ϕ0 ) ≤ (2m−1 − 2)2( 2 ) + 2m−1 − 1 = 2( 2 ) − 2( 2 )+1 + 2m−1 − 1 ≤ 2( 2 ) − 1,

m−1
m−1
and 2m−1 ≤ 2( 2 )+1 .
using that m
2
2 =m−1+
By Facts 2.1 and 4.1, TM ∈ SLk , where k = k(ϕ0 ) + max{k(ϕ1 ), k(ϕ2 )} + 1. Using that
|ϕ(Ai )| < |ϕ(A)|, we have
 m
 

m
k(ϕ0 ) + max{k(ϕ1 ), k(ϕ2 )} + 1 ≤ 2( 2 ) − 1 + (|ϕ(A)| − 2)2( 2 ) + 2m − 1 + 1 = k(ϕ). 

Now, to prove the theorem, let A be a generating set for S, define ϕ : A+ → 2S by ϕ(a) := {a}
for a ∈ A, and pick ψ : A+ → T as in the claim. Then Uϕ is the set of singletons, |ϕ(A)| = |A|,
|S|
and Sϕ = S, so that k(ϕ) = (|A| − 1)2( 2 ) + 2|S| − 1 =: k. Define the relational morphism
S
ρ: S →
7 T by ρ−1 (t) := ϕ(ψ −1 t). Then, for any SLk -pointlike X ⊆ S, we have X ⊆ ρ−1 (t)
for some t ∈ T , and therefore, since ρ−1 (t) lies in Sat(Uϕ ) by the claim, so does X. We
have proved that PLSLk (S) ⊆ Sat(Uϕ ), while the remarks at the beginning of this section
imply Sat(Uϕ ) ⊆ PLA (S), which is clearly contained in PLSLk (S), since SLk ⊆ A. Thus,
PLSLk (S) = Sat(Uϕ ) = PLA (S).

Acknowledgements
(|S2ϕ |)
In an earlier version of the proof of Theorem 4.3, we proved the claim for k(ϕ) := |ϕ(A)|2
.
We acknowledge the help of MathOverflow [12] for guiding us to the slightly better bound
given in the paper.
References
1. J. Almeida, Some algorithmic problems for pseudovarieties, Publ. Math. Debrecen 54 (1999), no. suppl.,
531–552, Automata and formal languages, VIII (Salgótarján, 1996).
2. K. Auinger and B. Steinberg, On the extension problem for partial permutations, Proc. Amer. Math. Soc.
131 (2003), no. 9, 2693–2703.
3. S. Eilenberg, Automata, languages, and machines. Vol. B, Academic Press, New York, 1976, With two
chapters by Bret Tilson, Pure and Applied Mathematics, Vol. 59.

8

SAMUEL J. V. GOOL AND BENJAMIN STEINBERG

4. K. Henckell, Pointlike sets: the finest aperiodic cover of a finite semigroup, J. Pure Appl. Algebra 55
(1988), 85–126.
5. K. Henckell, S. Lazarus, and J. Rhodes, Prime decomposition theorem for arbitrary semigroups: general
holonomy decomposition and synthesis theorem, J. Pure Appl. Algebra 55 (1988), no. 1-2, 127–172.
6. K. Henckell, J. Rhodes, and B. Steinberg, Aperiodic pointlikes and beyond, Internat. J. Algebra Comput.
20 (2010), no. 2, 287–305.
7. 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.
8. K. Krohn, J. Rhodes, and B. Tilson, Algebraic theory of machines, languages, and semigroups, Edited by
Michael A. Arbib. With a major contribution by Kenneth Krohn and John L. Rhodes, Academic Press,
New York, 1968, Chapters 1, 5–9.
9. T. Place and M. Zeitoun, Separating regular languages with first-order logic, Logical Methods in Computer
Science 12 (2016), no. 1:5, 1–30.
10. J. Rhodes and B. Steinberg, Pointlike sets, hyperdecidability and the identity problem for finite semigroups,
Internat. J. Algebra Comput. 9 (1999), no. 3-4, 475–481.
11.
, The q-theory of Finite Semigroups, Springer, 2009.
12. B. Steinberg, A strange two-variable recursion, MathOverflow question, answered by M. Fischler,
https://mathoverflow.net/q/278517.
, On pointlike sets and joins of pseudovarieties, Internat. J. Algebra Comput. 8 (1998), no. 2,
13.
203–234.
14. H. Straubing, Finite automata, formal logic, and circuit complexity, Progress in Theoretical Computer
Science, Birkhäuser Boston Inc., Boston, 1994.
15. T. Wilke, Classifying discrete temporal properties, STACS’99, Lec. Notes. Comp. Sci., vol. 1563, Springer,
1999, pp. 32–46.
Department of Mathematics, City College of New York, Convent Avenue at 138th Street, New
York, New York 10031, USA
E-mail address: samvangool@me.com and bsteinberg@ccny.cuny.edu

