Left-divisibility and word problems in single relation monoids

LetM be a monoid presented by <Σ;u=v> whereu andv are words on the finite alphabet Σ./ Deciding the world problem forM is still an open question, though it seems decidable and partial results exist. The remaining cases to solve are presentations of the form <a, b; bva=aua>,u, v∈{a, b}^⋆ The word problem is then closely related to the left-divisibility problem, as shown by S.I. Adjan who introduced a procedure that “almost” allows to decide the problem. The main contribution, due to Adjan and Oganesjan, states that ifbva is an unbordered factor ofaua then the word problem is deciable. We restrict Adjan's procedure to study the case whenbva is unbordered, which allows us to extend Adjan and Oganesjan's theorem. More specifically, we show (Proposition 4.24) that the word problem is decidable for presentations <a, b; bva=aua> with the only following condition: Inbva, the leftmost train ofb is strictly longer than the others. The following corollary naturally holds: The word problem is decidable for presentations of the form <a, b; b ^m a ⁿ =aua>,u∈{a, b}^⋆,m, n>0