Abstract. the properties of S depend on these

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

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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 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 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 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 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 .