# 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 $Δ=σ_{1}σ_{2}σ_{1}$.

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

A demonstration on a positive word. $σ_{2}σ_{1}σ_{1}σ_{2}σ_{1}σ_{1}σ_{1}σ_{1} =σ_{2}σ_{1}σ_{1}σ_{2}σ_{1}(σ_{1}σ_{1}σ_{1})=σ_{2}σ_{1}σ_{1}σ_{2}(σ_{1}σ_{1}σ_{1})σ_{1}=σ_{2}σ_{1}σ_{1}(σ_{2}σ_{1}σ_{1})σ_{1}σ_{1}=σ_{2}σ_{1}(σ_{1}σ_{2}σ_{1})σ_{1}σ_{1}σ_{1}=σ_{2}σ_{1}Δσ_{1}σ_{1}σ_{1}=σ_{2}σ_{1}Δ(σ_{1}σ_{1}σ_{1})=σ_{2}Δ(σ_{2}σ_{1}σ_{1})σ_{1}=Δ(σ_{1}σ_{2}σ_{1})σ_{1}σ_{1}=Δ_{2}σ_{1}σ_{1}=Δ_{2}(σ_{1}σ_{1}⋅1)=Δ_{2}σ_{1} $

I wrote a Haskell implementation of the algorithm.