Abstract. Every semigroup which is a finite disjoint union of copies of

the free monogenic semigroup (natural numbers under addition) has soluble word

problem and soluble membership problem. Efficient algorithms are given for both

problems.

1. Introduction

It is well known that some semigroups may be decomposed into a dis-

joint union of subsemigroups which is unlike the structures of classical al-

gebra such as groups and rings. For instance, the Rees Theorem states

that every completely simple semigroup is a Rees matrix semigroup over a

group G, and is thus a disjoint union of copies of G, see 7, Theorem 4.2.1;

every Clifford semigroup is a strong semilattice of groups and as such it is

a disjoint union of its maximal subgroups, see 7, Theorem IV.2.2; every

commutative semigroup is a semilattice of archimedean semigroups, see 5,

Theorem 3.3.1.

If S is a semigroup which can be decomposed into a disjoint union of

subsemigroups, then it is natural to ask how the properties of S depend on

these subsemigroups. For example, if the subsemigroups are finitely gen-

erated, then so is S. Arau ?jo et al. 3 consider the finite presentability of

? The author is financially supported by Princess Nourah bint Abdulrahman University in

Riyadh and Saudi Aramco Ibn Khaldun Fellowship for Saudi Women, in partnership with the

Center for Clean Water and Clean Energy at MIT.

Key words and phrases: semigroup, decidability, word problem, membership problem.

Mathematics Subject Classification: 20M05.

Acta Math. Hungar.

Acta Math. Hungar.

DOI: 10.1007/s10474-017-0687-5

DOI: 0

1

0236-5294/$20.00 ©?c 201A7kAadk ?eamd ?eiami iKaiiaKdi ?oa,dB ?o,uBdaupdeasptest, Hungary

N. ABUGHAZALAH

2

semigroups which are disjoint unions of finitely presented subsemigroups;

Golubov 4 showed that a semigroup which is a disjoint union of residually

finite subsemigroups is residually finite.

In the context where S is a semigroup which is a disjoint union of finitely

many copies of the free monogenic semigroup, the authors in 1 proved

that S is finitely presented and residually finite; in 2 the authors proved

that, up to isomorphism and anti-isomorphism, there are only two types of

semigroups which are unions of two copies of the free monogenic semigroup.

Similarly, they showed that there are only nine types of semigroups which

are unions of three copies of the free monogenic semigroup and provided

finite presentations for semigroups of each of these types.

In this paper we continue investigating finiteness conditions for a semi-

group which is a disjoint union of finitely many copies of the free monogenic

semigroup, the decidability of the word problem and membership problem

in particular.

The paper is organized as follows. In Section 2 we recall some lemmas

from 1 and explain the obtained results with clarify the strong regularities

which are all described in terms of arithmetic progressions. In Section 3 we

prove that S has a soluble word problem and soluble membership problem.

2. Properties of the semigroup which is a disjoint union of

finitely many copies of the free monogenic semigroup

Let S be a semigroup which is a disjoint union of finitely many copies of

the free monogenic semigroup:

S = Na ,

a?A

whereAisafinitesetandNa =?a?fora?A. Weprovedin1,Theorem3.1

that the semigroup S has the finite presentation

(1) A | akb = ?(a,k,b,1)?(a,k,b,1), (a,b ? A, k ? {1,2,…,j}) ,

for some ?(a,k,b,1) ? A and ?(a,k,b,1) ? N.

We introduce the necessary lemmas from 1 to add more information to

the presentation (1).

Lemma 2.1 (1, Lemma 2.4). If apx = br, ap+qx = br+s for some

a,b?A,x?S,p,q,r?N,s?N0,thenap+qtx=br+st forall t?N0.

Lemma2.2. Leta,c?A,b?S. Ifapb=cnp fortwodistinctvaluesofp

then there exists an arithmetic progression p + qn, r ? N, s ? N ? {0} such

that ap+qnb = cr+sn for every n ? {0,1,2,…}.

Acta Mathematica Hungarica

CONCRETE ALGORITHMS FOR WORD PROBLEM AND SUBSEMIGROUP PROBLEM

3

Proof. Since, apb = cnp for two distinct values of p, then we have q, r

suchthataqb=cnq,arb=cnr whereq?randr?qisassmallaspossible.

Hence, by Lemma 2.1, ar+n(r?q)b = cnr+n(nr?nq) holds for every n ? N.

Lemma 2.3. Let a, c ? A, b ? S. Suppose q ? N is the smallest possible

number such that apb = cr, ap+qb = cr+s for some p,r ? N,s ? N?{0} holds

in S. Then if i?{p+1,p+2,…,p+q?1} and aib=dt we have d?=c.

Proof. Suppose to the contrary that d = c then we have

(i) apb = cr;

(ii) aib = ct;

(iii) ap+qb = cr+s.

Case 1. If t ? r then from (i), (ii) and Lemma 2.1, we obtain an arith-

metic progression with a difference i ? p ? q, a contradiction.

Case 2. If t < r then from (ii), (iii) and Lemma 2.1, we obtain an arith-
metic progression with a difference p + q ? i ? q, a contradiction.
Definition 2.4. An arithmetic progression is a sequence of the form
ak, ak+q, ak+2q, ... where a ? A, k,q ? N (so that the difference of any two
consecutive powers is constant), and we call it a minimal arithmetic progres-
sion if q is the smallest possible number such that akb = cr, ak+qb = cr+s for
some k, r ? N, s ? N ? 0.
Definition 2.5. The interval on Na of length L is the set
I=at,at+L= ah ?Na :t?h?t+L .
Lemma 2.6. There exists P ? N such that the following holds. For every
(not necessarily distinct) a,b ? A, and every x ? S, if ar and as (r < s) are
thefirsttwopowersofasuchthatarx,asx?Nb thens?r?P.
Proof. Consider x to be arbitrary but fixed. Within Na there are at
most n = |A| minimal arithmetic progressions by Lemmas 2.1, 2.3, one for
each Nb, b ? A. So we have sets Aci for ci ? {c1,c2,...,cm} ? A where
each Aci is the set of elements ak such that ak x = cri , with the differences
d1 ? d2 ? ··· ? ds ? ··· ? dm respectively. Thus,
Na =H?Ac1 ?Ac2 ?···?Acs ?···?Acm
whereH={a,a2,...,ap}andAcs ={aps,aps+ds,...}suchthatps=p+s
for every 1 ? s ? m and then Ac1 ?Ac2 ?···?Acs ?···?Acm contains all but
finitely many elements of Na which is H by Lemma 2.1. Now, we prove that
there exists P ? N not dependent on x, such that ds ? P and this is sufficient
since a,b ? A, A is finite and by taking the maximum of P over all a,b will
do for all. Let us consider an interval I on Na of length L = d1d2 . . . ds?1
which occurs at the point apM +1 where pM is the maximum power among
{p1,p2,...,ps,...,pm}.
Acta Mathematica Hungarica
N. ABUGHAZALAH
4
Claim. I must contain at least one element from Acs ? Acs+1 ? · · · ? Acm .
Proof. Suppose to the contrary that all the elements in I belong to
Ac1 ? Ac2 ? · · · ? Acs?1 . Since Ai is an arithmetic progression with a differ-
encedi(1?i?s?1),andsincedi|LitfollowsthatAci+L ?Aci.Hence,
ifI?Ac1 ?Ac2 ?···?Acs?1,itfollowsthatI·aL ?Ac1 ?Ac2 ?···?Acs?1,
andsoI·auL ?Ac1 ?Ac2 ?···?Acs?1 forallu?N. SinceI isaninterval
of length L, it follows that u?N(I · auL) contains all but finitely many ele-
ments of N. This contradicts the fact that Acs is an infinite set disjoint from
all Ac1, Ac2, ..., Acs?1.
Now we prove the lemma by induction on s. If s = 1 then we choose
L=1. Assume that the statement holds for every k?s?1. As a re-
sult of our claim, an interval J of length tL can be viewed as a disjoint
union of t intervals of length L. Each of the latter contains elements from
Acs ? · · · ? Acm , and so J contains at least t such elements. Suppose that
ds >L(m+1). So the interval ar,ar+L(m+1) contains at least m+1 el-

ements from Acs ? Acs+1 ? ··· ? Acm and no elements from Acs . Then by

using the pigeonhole principle, we conclude that two elements come from

the same Act (s < t ? m) with a difference less than ds, a contradiction.
Thus ds ? L(m + 1) ? L(n + 1). Since the number L is dependent on d1,
. . . , ds?1, none of them is dependent on x by the induction hypothesis and
by replacing m by n which is independent of x, we get P = L(n + 1) which
does not depend on x.
The preceding result means that the differences of all minimal arithmetic
progressions arising in Lemma 2.1 are uniformly bounded.
In the next lemma we prove that there is a uniform bound to how far
arithmetic progressions can start.
Lemma 2.7. There exists Q ? N such that the following holds. For every
a,b?A,andeveryx?S,ifar and as (r~~ k, such that aT ?hdx, aT ?kdx belong to the same Nc with a difference~~

(h ? k)d where b ?= c and that is clear because aT ?hd, aT ?kd appear before

Acta Mathematica Hungarica

CONCRETE ALGORITHMS FOR WORD PROBLEM AND SUBSEMIGROUP PROBLEM

5

aT , aT +d where they are the first two powers such that (2) holds. There-

fore, aT +2(h?k)dx ? Nc but this element also belongs to Nb where the power

T +2(h?k)d?{T,T +d,…,T +md,…}(m?N), a contradiction.

Lemma 2.8. As x = bs ranges over all of S, only finitely many arith-

metic progressions arise in Lemma 2.1.

Proof. Immediate consequence of Lemmas 2.6, 2.7 in which all these

arithmetic progressions start within a bounded range and their periods are

bounded as well.

3. Decidability for S

3.1. Word problem. A semigroup S generated by a finite set A has

soluble word problem (with respect to A) if there exists an algorithm which,

for any two words u, v ? A+ , decides whether the relation u = v holds in S

or not. For finitely generated semigroups it is easy to see that solubility of

the word problem does not depend on the choice of (finite) generating set

for S. We write w1 ? w2 if the words w1 and w2 are identical, and w1 = w2

if they represent the same element of S.

Remark 3.1. It is well known that finitely presented residually finite

semigroups have soluble word problem 4, and from our results in 1, the

semigroup under consideration in this paper is finitely presented and resid-

ually finite and then has soluble word problem. However, we give a concrete

algorithm which is much more efficient than the generic one in the following

theorem.

Theorem 3.2. Every semigroup which is a disjoint union of finitely

many copies of the free monogenic semigroup has soluble word problem.

Proof. Let S = a?A Na, and Na = ?a?. Thus the Algorithm is as fol-

lows:

Input: u,v?A+ andu?xi1xi2 ···xim andv?yj1yj2 ···yjn,wherex ,y

12m 12n kl

? A for every 1 ? k ? m and 1 ? l ? n.

Output: u = v or u ?= v in S.

The idea of the Algorithm is to reduce the word u to an equivalent word

ak forsomea?Aandk?N.

Step 1.

Lemma 3.3. If we have a presentation on S of the form

(3) A | akb = ?(a,k,b,1)?(a,k,b,1), (a,b ? A, k ? {1,2,…,j}) ,

for some ?(a,k,b,1) ? A and ?(a,k,b,1) ? N, then there is an algorithm that

reduces any word of the form aib to a word of the form cj where a,b,c ? A

and j ? N.

Acta Mathematica Hungarica

N. ABUGHAZALAH

6

Proof. We specify the presentation (3) as follows. Firstly, notice that

the relations in the presentation are of the form xiy = zj where x, y, z ? A

and i, j ? N and thus we have at most n(n ? 1) minimal arithmetic pro-

gressions in which we get at most n(n ? 1) differences. Take the the least

common multiple (LCM) of all these differences D. Thus

Ra? ,b = aib = ?(a,i,b,1)?(a,i,b,1) : i = 1,…,r(a,b) ,

Wherer(a,b)?Q=(n+1)P from2.6,2.7.

r(a ,b)+D k ?(a,k,b,1)

(4) Ra,b = a b=?(a,k,b,1) ,

k=r(a,b)+1

ak+Db=?(a,k+D,b,1)?(a,k+D,b,1) ,

and then we get the required presentation as

R = ( R a? , b ? R a , b ) ,

a,b?A

where k = lD, l is any natural number. Notice that from (4) we have

(5) ak+Db=aDakb=aD?(a,k,b,1)?(a,k,b,1) =?(a,k+D,b,1)?(a,k+D,b,1)

So within Na we have Pt arithmetic progressions, where t is the remain-

der of division of r(a, b) + q by D for every q ? {1, 2, . . . , D} as follows:

P0 = ar(a,b)+1,ar(a,b)+1+D,ar(a,b)+1+2D,… ,

P1 = ar(a,b)+2,ar(a,b)+2+D,ar(a,b)+2+2D,… ,

.

PD?1 = ar(a,b)+D,ar(a,b)+2D,ar(a,b)+3D,… .

Thus for every i ? N every word of the form aib is reduced to a word of the

formcj.

Step 2.

Lemma 3.4. For a, b ? A and s ? N, a finite number of applications of

relations in R transforms asb to

?(a, r(a, b) + t + 1 + f D, b, 1)?(a,r(a,b)+t+1+f D,b,1)

where ?(a,r(a,b)+t+1+fD,b,1)?A and ?(a,r(a,b)+t+1+fD,b,1)

? N.

Acta Mathematica Hungarica

CONCRETE ALGORITHMS FOR WORD PROBLEM AND SUBSEMIGROUP PROBLEM

7

Proof. If the relation

asb = ?(a,r(a,b) + t + 1 + fD,b,1)?(a,r(a,b)+t+1+fD,b,1)

belongs to R, we are done. Now, suppose that the given relation does not

appear in R, that means s > k where k = lD for some l and then s = hD + t

where 0 ? t < D and thus as ? Pt. Notice that Pt starts with the two ele-
ments ar(a,b)+(t+1), ar(a,b)+(t+1+D) and by doing some calculations as follows:
First we know that s = hD + t, and
s ? r(a, b) ? t ? 1 = hD + t ? r(a, b) ? t ? 1 = f D
forsomef. Thus,hD=fD+r(a,b)+1. So,
s = r(a, b) + t + 1 + f D,
which means that as is in the f position. Hence,
asb = afD+r(a,b)+t+1b ? aDaD ···aD ar(a,b)+t+1b
f times
= aDaD · · · aD ?(a, r(a, b) + t + 1, b, 1)?(a,r(a,b)+t+1,b,1)
f times
= aD · · · aD ?(a, r(a, b) + t + 1 + D, b, 1)?(a,r(a,b)+t+1+D,b,1)
(f?1) times
= ?(a, r(a, b) + t + 1 + f D, b, 1)?(a,r(a,b)+t+1+f D,b,1)
by (4) and (5). Therefore, we can obtain
?(a, r(a, b) + t + 1 + f D, b, 1)?(a,r(a,b)+t+1+f D,b,1)
in finitely many steps.
Step 3. Transform u to its normal form as follows:
u ? xi1xi2 ···xim ? (xi1x )xi2?1 ···xim
.
12m122m
= xi12xi2?1 ···xim ? (xi12x )xi2?2 ···xim
i122 m i1222 m
by Lemma 3.4. So, by taking the first power xi1 with the next element x2
1
and doing this i2 steps, we get rid of xi2 and using the same process with all
2
xi3, xi4, ..., xim, we end up with xIM after i +i +···+i steps. So we
34m I23m
have u = xIM .
I
Acta Mathematica Hungarica
N. ABUGHAZALAH
8
Step 4. Transform v to its normal form xJN analogously to Step 3.
J
Step5.IfI=JandIM =JN thenu=v,otherwiseu?=v.
Therefore, S has soluble word problem.
3.2. Subsemigroup membership problem. Let S be a finitely
generated semigroup. We say that S has a soluble subsemigroup mem-
bership problem if there is an algorithm that takes as input a finite set
Y = {y1,y2,...,yk} ? S and an element x ? S and decides whether x is in
the subsemigroup T generated by Y .
Now we introduce necessary well-known theorems about subsemigroups
of the natural number semigroup N. We will use these theorems to devise
an algorithm to solve the subsemigroups membership problem for the semi-
group under consideration.
Theorem 3.5 6, Theorem 1. Let S be a subsemigroup of N, then
(i) There is s ? N such that for n ? s, n ? S, or
(ii) There is n?N, n>1 such that n is a factor of all s?S.

Proof. We prove this Theorem as the proof itself leads us to Corol-

lary 3.10.

Assume that there exist s1,s2,…,sm ?S such that the g.c.d. of the

collection (s1, s2, . . . , sm) is 1. Let S? be the subsemigroup of N generated

by {s1,s2,…,sm}, notice that S? ? S. Let s = 2s1s2 ···sm and for b > s,

since the g.c.d. of (s1,s2,…,sm) is 1, we may find integers ?1,?2,…,?m

such that ?1s1 + · · · + ?msm = b. Hence there exist integers qi and ri such

that ?i = qis1 …si?1si+1 …sm +ri where 0 < ri ? s1 ...si?1si+1 ...sm (i =
2,3,...,m). Now put
?1 =?1 +(q2 +···+qm)s2s3...sm, ?i =ri, (i=2,3,...,m).
Thus b = ?1s1 +?2s2 +···+?msm. Note that ?i > 0 for i = 2,3…,m. But

since

?2s2 +···+?msm =r2s2 +···+rmsm ?2s1s2…sm ** 0. **

Thus there are two types of subsemigroups of N. The first type con-

tains all natural numbers greater than some fixed natural number, and will

be called relatively prime subsemigroups of N. The second type is a fixed

integral multiple of a relatively prime subsemigroup.

Corollary 3.6. Every subsemigroup of N is finitely generated.

Remark 3.7. This corollary is well known and here is an easy proof.

Acta Mathematica Hungarica

CONCRETE ALGORITHMS FOR WORD PROBLEM AND SUBSEMIGROUP PROBLEM

9

Proof. Suppose that S is a subsemigroup of N and the greatest com-

mon divisor of S is 1. Thus the generating set for S is S?{1,2,…,2k}

wherek?Nsuchthatforeveryn?k: n?S. Indeedthisissobecauseif

m > 2k then m = qk + f. Thus

m=(q?1)k+k+f wherek+f?S?{1,2,…,2k}.

If S is a subsemigroup of N then the greatest common divisor (g.c.d.) of

S is the g.c.d. of the generator set of S.

Corollary 3.8. Every subsemigroup of N has the form F ? DN ,d,

where F is a finite set and DN ,d = {da : a ? N }.

Definition 3.9. Suppose that the semigroup S is generated by {n1, n2,

…,nk}. If there exist two elements d,N ? S and a set F ? S such that

(6) F =S?{1,2,…,N ?1};

(7) S?{N,N +1,…}= dk:k?N, dk?N ,

then we say that S is defined by the triple d,N,F.

Corollary 3.10. Suppose that S is a subsemigroup of the natural num-

ber semigroup N. Suppose that S is generated by n1,n2,…,nk. Then S is

defined by the triple d,N,F where d is the greatest common divisor of

{n1,n2,…,nk},N=2dn1n2···nk,and F?{1,2,…,N?1}.

Proof. Follows immediately from Theorem 3.5 and Corollary 3.6.

Corollary 3.11. Suppose that S is a subsemigroup of the free mono-

genicsemigroupN. SupposethatSisgeneratedbyan1,an2,…,ank. ThenS

is defined by the triple d,N,F where d is the greatest common divisor of

{an1,an2,…,ank}, N =a2dan1an2 ···ank, and F ?{a,a2,…,aN?1}.

Proof. Directly by Corollary 3.10.

After understanding how subsemigroups of N behave we are ready to

startdesigningthealgorithm. SinceS=N1?N2?···?Nn,andT isa

subsemigroup of S, then T =T1 ?T2 ?···?Tm, where Ti ?Ni for every

i ? {1,2,…,m}, m ? n. Consequently, the generator set for T is

AT = ATi,

i?{1,2,…,m}

where ATi is the generator set of Ti for every i ? {1,2,…,m}. Thus T is

finitely generated (3, Proposition 3.1).

Acta Mathematica Hungarica

N. ABUGHAZALAH

10

Lemma 3.12. Suppose that the subsemigroup Uj = ?Nj ? AT ? is defined

by the triple dj,Nj,Fj. Then there is an algorithm which takes arbitrary

Ui, Uj and b?AT and tests whether Uib?Nj ?Uj or not.

Proof. Letarj ?Uib?Nj. Then

ar?U ??ar?F orar=adjhj forsomedh ?dt wheredt =N,

jj jjjj jjjj jjj

by Corollary 3.10.

Theorem 3.13. Every semigroup which is a disjoint union of finitely

many copies of the free monogenic semigroup has a soluble subsemigroup

membership problem.

Proof. Let S be such a semigroup. Then the Algorithm is as follows:

Input. A finite set AT ? S, specified as normal form words over the

generating set, and an element x ? S, specified as a normal form word.

Output. Whether x ? T where T is the subsemigroup of S generated

by AT .

Step 1. Take Ui = ?Ai? = ?Ni ? At?, which means that Ui is a finitely

generated subsemigroup of Ni and then is defined by the triple di, Ni, Fi by

Corollary 3.11. Now check if (U1,U2,…,Um) = T, where (U1,U2,…,Um) =

U1 ?U2 ?···?Um, which means check whether

m

Uix ? Ui for every i ? {1, 2, . . . , m} and for every x ? AT ,

i=1

byLemma3.12. IfyesthengotoStep4. Iftherewasarix=arj andarj ??Uj

then go to Step 2.

Step 2. Add the missing element arj to Uj and then we have U(+1) =

?AUj ?arj?, which is defined by the triple d(+1),N(+1),F(+1). Notice that

j jjj

by adding arj to Uj we reduce the gaps in Fj or we reduce the difference dj

j

by Corollary 3.8. Thus we get the new description

(8) U1,U2,…,Uj?1,U(+1),Uj+1,…,Um .

Step 3. We start again with the new description (8) and we keep adding

these missing elements with all i ? {1, 2, . . . , m}. And then we reach to the

final description

U(+s1),U(+s2),…,U(+sj),…,U(+sm) = T.

12jm

Which means that U(+sj)b ? m U(+si) for every b ? AT and for every

j i=1i

j ? {1, 2, . . . , m} and that because as we explained before each Uj is defined

Acta Mathematica Hungarica

j

ijj

jj

CONCRETE ALGORITHMS FOR WORD PROBLEM AND SUBSEMIGROUP PROBLEM

11

by the triple dj,Nj,Fj . So if we add an element arj to Uj that means,

j

by Corollary 3.8, we reduce the gaps in Fj and they are finite, or we reduce

the difference dj and we can do this just finitely often. Thus we add finitely

many elements in each Uj, which implies that this process terminates. So

now each U(+sj) is defined by the triple

j

d(+sj),N(+sj),F(+sj) .

jjj

Step 4. If we were given x=arh ?S and we want to see if x?T or

h

not then we just take this element and see in U(+sh) if arh ?F(+sh), or

hhh

rh = d(+sh)k for some d(+sh)k ? d(+sh)t where d(+sh)t = N(+sh), then x ? T

hhhhh

otherwise x ?? T .