Linear time algorithm for the word problem on $B_3$

The word problem is solved if one can put $w$ in Garside normal form. The process is trivial in $B_3$ and can be done in linear time on a Turing machine. Remember $\Delta ={\sigma }_1{\sigma }_2{\sigma }_1$.

1. Rewrite all generator with negative exponents into ones with positive exponents and a ${\Delta }^{-1}$.
2. Move every ${\Delta }^{-1}$ to the beginning of the word. First locate the last ${\Delta }^{-1}$, and move it forward using the relations ${\Delta }^{2n+1}{\sigma }_i={\sigma }_{3-i}{\Delta }^{2n+1}$ and ${\Delta }^{2n}{\sigma }_i={\sigma }_i{\Delta }^{2n}$. Pick up other ${\Delta }^{-1}$’s in between.
3. Move every $\Delta$ factor in the word to the beginning of the word. Read from the end of the word, move it forward using $\Delta$ relations, pick up other $\Delta$ on the way. Check if moving $\Delta$ generates another $\Delta$. $B_3$ don’t have ${\sigma }_i{\sigma }_j={\sigma }_j{\sigma }_i$ relation, therefore if a new $\Delta$ is created from moving $\Delta$’s around, it is a local event. To be precise, during this process, $x{\Delta }^{m}y=x{\Delta }^{m+1}{y}^{\prime }$ if and only if the first 3 letter in the current presentation of $y$ is $\Delta$.

A demonstration on a positive word. $$\begin{array}{rl}{\sigma }_2{\sigma }_1{\sigma }_1{\sigma }_2{\sigma }_1{\sigma }_1{\sigma }_1{\sigma }_1& ={\sigma }_2{\sigma }_1{\sigma }_1{\sigma }_2{\sigma }_1({\sigma }_1{\sigma }_1{\sigma }_1)\\ & ={\sigma }_2{\sigma }_1{\sigma }_1{\sigma }_2({\sigma }_1{\sigma }_1{\sigma }_1){\sigma }_1\\ & ={\sigma }_2{\sigma }_1{\sigma }_1({\sigma }_2{\sigma }_1{\sigma }_1){\sigma }_1{\sigma }_1\\ & ={\sigma }_2{\sigma }_1({\sigma }_1{\sigma }_2{\sigma }_1){\sigma }_1{\sigma }_1{\sigma }_1\\ & ={\sigma }_2{\sigma }_1\Delta {\sigma }_1{\sigma }_1{\sigma }_1\\ & ={\sigma }_2{\sigma }_1\Delta ({\sigma }_1{\sigma }_1{\sigma }_1)\\ & ={\sigma }_2\Delta ({\sigma }_2{\sigma }_1{\sigma }_1){\sigma }_1\\ & =\Delta ({\sigma }_1{\sigma }_2{\sigma }_1){\sigma }_1{\sigma }_1\\ & ={\Delta }^2{\sigma }_1{\sigma }_1\\ & ={\Delta }^2({\sigma }_1{\sigma }_1\cdot 1)\\ & ={\Delta }^2{\sigma }_1^2\end{array}$$