Rewrite systems for the positive braid semigroups (Q1345735)

The author considers the semigroup \(P_3=\langle a, b \mid aba=bab\rangle\) of positive braids on 3 strands, and its generalizations \(P_n\) for \(n \geq 3\). It was shown by \textit{D. Kapur} and \textit{P. Narendran} [Theor. Comput. Sci. 35, 337-344 (1985; Zbl 0588.03023)] that the semigroup \(P_3\) has no finite complete rewriting system. In the present paper \(P_3\) is shown to have a complete left regular rewrite system. Here a left regular rewrite system over a finite alphabet \(A\) consists of a finite set of rules \(U \to V\) after \(L\), where \(U\) and \(V\) are words and \(L\) is a regular language. Such a rule allows a reduction \(XUY \to XVY\) if the word \(X\) is in \(L\). The system is complete for a semigroup \(S\) with generators \(A\) if each sequence of reductions is finite, and two words reduce to the same irreducible word just in case they represent the same element of \(S\). For \(P_3\) a complete left regular system is given by the following two rules: (1) \(bab \to aba\) after \(a^*(bb^* aaa^* b)^* b^*\), (2) \(aba \to bab\) after \(a^* bb^* a(aa^* bbb^* aa^*)^* a^*\). In this system a word is reduced to the unique lexically smallest word that represents the same element in \(P_3\).