
Printable version (pdf)Divisibility Problem for one relator Monoids
We consider monoids presented by one defining relation in 2 generators: M = < a, b; aU = bV>. (1) Denote A_{1} = aU and A_{2} = 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 1relator 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 = P_{1}P_{2} ... P_{k}P_{k+1}, (2) where each P_{i} is the maximal nonempty proper common prefix of the word P_{i}P_{i+1} ... P_{k+1} and the appropriate relator aU or bV, or of the form aW = P_{1}P_{2} ... P_{k}A_{jk}W_{k+1}, (3) 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_{1} and denote it by P_{1} = MCP(aW, A_{1}). (4) We have aW = P_{1}W_{1} and aU = P_{1}U_{1 } for some W_{1} and U_{1}. Clearly P_{1} is not empty. We consider the following 2 cases. Case 1. If U_{1} is empty, then aW = aUW_{1}. 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_{1} in M. Hence aW is left side divisible by b in M. Case 2. Let U_{1} be not empty. Then P_{1} is a proper prefix of aU. If W_{1} is empty then aW is a proper segment of the relator aU. It is easy to prove that the proper segment P_{1} of aU is not divisible by b in M. Hence we can assume that U_{1} and W_{1} 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_{1} of aU in P_{1}W_{1} to the right side we should divide W_{1} by b if it starts by a or divide W_{1} 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_{2} = MCP(W_{1 }, A_{j}), where A_{j1 } is the relator of M which has a common initial letter with W_{1}. Suppose W_{1} = P_{2}W_{2} and A_{j} = P_{2}U_{2}. Then again we consider 2 cases. Case 2.1. If U_{2} is empty, then W_{1} = A_{j}W_{1}. In this case we have the following prefix decomposition of the word aW: aW = P_{1}A_{j1}W_{2}, where A_{j1 } is called the head. Case 2.2. Let U_{2} be nonempty. In this case if W_{2} is empty then aW = P_{1}P_{2} where P_{2} 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_{1}P_{2} is not divisible by b in M. Hence we can assume that U_{2} and W_{2} 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_{2} of A_{j1 }in P_{1}P_{2}W_{2} we should divide W_{2} by b if it starts by a, or divide W_{2} 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_{3} = MCP(W_{2 }, A_{j2 }), where A_{j2} is one of the relators of M which has the common initial letter with the word W_{2}. 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: aW = P_{1}P_{2} ...P_{k}aUW_{k+1}® P_{1}P_{2} ...P_{k}bV W_{k+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
2. Adian S.I. (1976). Word transformations in a semigroup that is given by a system of defining relations. Algebra i Logika 15, 611621; 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, 412421; 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. 207296.
