# 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'$$ if and only if the first 3 letter in the current presentation of $$y$$ is $$\Delta$$.
A demonstration on a positive word. \begin{align*} \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{align*} I wrote a Haskell implementation of the algorithm.
Posted by Chao Xu on 2011-07-05.
Tags: braid group, BSU REU, computational complexity.