Divisibility Problem for one relator Monoids

We  consider monoids presented by one defining relation in 2 generators:

Denote A₁ = aU and A₂ = bV.

We say that the word X is left side divisible by Y in M if there exists a word Z such that X = YZ in M. The left side divisibility problem for M is the requirement to find an algorithm to recognize for any two words X and Y, whether or not X is left side divisible by Y in M?

The following theorem was proved in [1,2,3].

Theorem 1  The word problem for any 1-relator monoids can be reduced to the left side divisibility problem for monoids M presented in 2 generators by 1 defining relation of the form aU = bV. For the solution of this problem it sufficies to find an algorithm to recognize for any word aW (or for any word bW) whether or not it is left side divisible in M by the letter b (accordingly by the letter a).

The algorithm  was introduced in [2] for a more general case of monoids presented by any cyclefree system of relations. Here we shall apply this algorithm to the case of the monoid M.

The algorithm  was used in several papers for a solution of the left side divisibility problem for monoids M under some additional conditions.

To apply this algorithm one should find another algorithm  that decides for any word aW, whether or not the algorithm  terminates when applied to aW.

For the given word aW the algorithm  finds the uniquely defined prefix decomposition which is either of the form

where each P_i is the maximal nonempty proper common prefix of the word P_iP_i+1 ... P_k+1 and the appropriate relator aU or bV, or of the form

where the prefixes P_i are defined in a similar way, but the segment A_jk is one of the relators of the monoid M. We call the segment A_jk the head of the decomposition (3).

Let us describe in details how our algorithm  works.

Suppose we have an initial word aW. Consider the Maximal Common Prefix of two words aW and A₁ and denote it by

We have  aW = P₁W₁ and  aU = P₁U₁  for some W₁ and U₁.

Clearly P₁ is not empty. We consider the following 2 cases.

Case 1. If U₁ is empty, then aW = aUW₁. So we have a prefix decomposition of the form (3) for k=0.

In this case the algorithm  replaces in aW the segment aU by bV. So we obtain aW = bVW₁ in M. Hence aW is left side divisible by b in M.

Case 2. Let U₁ be not empty. Then P₁ is a proper prefix of aU.

If W₁ is empty then aW is a proper segment of the relator aU. It is easy to prove that the proper segment P₁ of aU is not divisible by b in M.

Hence we can assume that U₁ and W₁ both are nonempty. It follows from (4) that in this case they have different initial letters a and b.

In this case to prolong the prefix P₁ of aU in P₁W₁ to the right side we should divide W₁ by b if it starts by a or divide W₁ by a if it starts by b. So the situation is similar to the initial one.

Now in a similar way we consider the nonempty word P₂ = MCP(W₁ , A_j), where A_j1  is the relator of M which has a common initial letter with W₁.

Suppose W₁ = P₂W₂ and A_j = P₂U₂. Then again we consider 2 cases.

Case 2.1. If U₂ is empty, then W₁ = A_jW₁.

In this case we have the following prefix decomposition of the word aW:

where A_j1  is called the head.

Case 2.2. Let U₂ be nonempty.

In this case if W₂ is empty then  aW = P₁P₂ where P₂ is a proper segment of of the relator A_j1 . Hence we obtained for aW a prefix decomposition of the form (2). It is easy to prove that the word P₁P₂ is not divisible by b in M.

Hence we can assume that U₂ and W₂ both are nonempty. It follows from (4) that in this case they have different initial letters a and b.

In this case to prolong the prefix P₂ of  A_j1 in P₁P₂W₂ we should divide W₂ by b if it starts by a, or divide W₂ by a if it starts by b. So the situation again is similar to the initial one.

Hence we can consider the nonempty word P₃ = MCP(W₂ , A_j2 ), where A_j2 is one of the relators of M which has the common initial letter with the word W₂. And so on. The length of the word W_i is decreasing. So after a finite number of steps either we shall find some prefix decomposition of the form (3) with the head A_jk or we shall stop on some decomposition of the form (2).

It is easy to prove that if the decomposition of aW is of the form (2), then the word aW in M is not left side divisible by b.

If the decomposition is of the form (3), then the algorithm  replaces the head A_i in aW by the another relator in (1): aU should be replaced by bV or bV by aU. Hence we get one of the following elementary transformations in the monoid M:

Clearly the result W' of this transformation is equal to aW in M. If the resulting word W' starts by the letter b (this happens only if k=0!), then the algorithm  terminates by the positive answer. Otherwise the algorithm  repeats the same procedure with the word W'.

Theorem 2  (see [2]) If the word aW is left side divisible by b in M then the algorithm (aW) terminates with the positive result, and in this case we obtain the shortest proof of the left side divisibility of the word aW by b in M.

Conjecture 1  There exists an algorithm  that decides for any word aW whether or not the algorithm (aW) terminates.

Problem 1  Check if the conjecture 1 is true.
 

1    Adian S.I. (1966). Defining relations and algorithmic problems for groups and semigroups.  Proc. Steklov Inst. Math. 85. (English version published by the American Mathematical Society, 1967).

2.    Adian S.I. (1976). Word transformations in a semigroup that is given by a system of defining relations.  Algebra i Logika 15, 611-621; English transl. in  Algebra and Logic 15 (1976).

3.    Adian S.I. and Oganesian G.U. (1987). On the word and divisibility problems in semigroups with one defining relation. Mat. Zametki 41, 412-421; English transl. in Math. Notes 41 (1987).

4.    Adian S.I. and V.G.Durnev. Decision problems for groups and semigroups. In "Russian Math. Surveys" (Uspechi Mat. Nauk, 2000), vol. 55, No. 2, pp. 207-296.