Main page

Adian's problem

Previous conferences

Program committee

Invited speakers

Submissions

Program

Organizers

Scholarships

Registration

Accommodations

Information and Maps

Photos

Printable version (pdf)

Divisibility Problem for one relator Monoids


S.I.Adian
Steklov Mathematical Institute
Gubkina str. 8, 117966 Moscow, RUSSIA
 e-mail: si@adian.mian.su



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

M = < a, b; aU = bV>.                              (1)

Denote A1 = aU and A2 = 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).

      Algorithm 

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

aW = P1P2 ... PkPk+1,                               (2)

where each Pi is the maximal nonempty proper common prefix of the word PiPi+1 ... Pk+1 and the appropriate relator aU or bV, or of the form

aW = P1P2 ... PkAjkWk+1,                          (3)

where the prefixes Pi are defined in a similar way, but the segment Ajk is one of the relators of the monoid M. We call the segment Ajk 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 A1 and denote it by

P1 =  MCP(aW, A1).                                   (4)

We have  aW = P1W1 and  aU = P1U for some W1 and U1.

Clearly P1 is not empty. We consider the following 2 cases.

Case 1. If U1 is empty, then aW = aUW1. 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 = bVW1 in M. Hence aW is left side divisible by b in M.

Case 2. Let U1 be not empty. Then P1 is a proper prefix of aU.

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

Hence we can assume that U1 and W1 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 P1 of aU in P1W1 to the right side we should divide W1 by b if it starts by a or divide W1 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 P2 = MCP(W1 , Aj), where Aj is the relator of M which has a common initial letter with W1.

Suppose W1 = P2W2 and Aj = P2U2. Then again we consider 2 cases.

Case 2.1. If U2 is empty, then W1 = AjW1.

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

aW = P1Aj1W2,

where Aj is called the head.

Case 2.2. Let U2 be nonempty.

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

Hence we can assume that U2 and W2 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 P2 of  Aj1 in P1P2W2 we should divide W2 by b if it starts by a, or divide W2 by a if it starts by b. So the situation again is similar to the initial one.

Hence we can consider the nonempty word P3 = MCP(W2 , Aj2 ), where Aj2 is one of the relators of M which has the common initial letter with the word W2. And so on. The length of the word Wi is decreasing. So after a finite number of steps either we shall find some prefix decomposition of the form (3) with the head Ajk 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 Ai 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:

aW = P1P2 ...PkaUWk+1® P1P2 ...PkbV Wk+1 = W'

or
aW = P1P2 ...PkbVWk+1® P1P2 ...PkaUWk+1 = W'.

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.
 

REFERENCES


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.