A new approach to the word and conjugacy problems in the braid groups (Q1273842)

The \(n\)-string braid group \(B_n\) has the presentation: \[ \langle\sigma_1,\dots,\sigma_{n-1};\;\sigma_i\sigma_j=\sigma_j\sigma_i\;(|i-j|>1),\;\sigma_i\sigma_j\sigma_i=\sigma_j\sigma_i\sigma_j\;(|i-j|=1)\rangle. \] This presentation is usually called the Artin presentation. The authors propose a new presentation as follows: \[ \begin{aligned}\langle a_{ts} (1\leq s < t\leq n);\;a_{ts} a_{rq}&=a_{rq}a_{ts} (t-r)(t-q)(s-r)(s-q)>0,\\ a_{ts}a_{sr}&=a_{tr}a_{ts}=a_{sr}a_{tr} (1\leq r<s<t\leq n)\rangle,\end{aligned} \] where \(a_{ts}\) are defined by \(a_{ts}=(\sigma_{t-1}\sigma_{t-2}\cdots\sigma_{s+1})\sigma_s(\sigma_{s+1}^{-1}\cdots\sigma^{-1}_{t-2}\sigma^{-1}_{t-1})\). The authors show that this presentation retains most of the desirable features of the Artin presentation, and at the same time makes certain computational improvements possible. Using the new presentation, the authors give a polynomial time algorithm for the word problem and also an algorithm for the conjugacy problem in the braid groups.