The Art Gallery Guardian

Linear time algorithm for the word problem on B3B_3

The word problem is solved if one can put ww in Garside normal form. The process is trivial in B3B_3 and can be done in linear time on a Turing machine. Remember Δ=σ1σ2σ1\Delta = \sigma_1\sigma_2\sigma_1.

  1. Rewrite all generator with negative exponents into ones with positive exponents and a Δ1\Delta^{-1}.
  2. Move every Δ1\Delta^{-1} to the beginning of the word. First locate the last Δ1\Delta^{-1}, and move it forward using the relations Δ2n+1σi=σ3iΔ2n+1\Delta^{2n+1}\sigma_i = \sigma_{3-i} \Delta^{2n+1} and Δ2nσi=σiΔ2n\Delta^{2n}\sigma_i = \sigma_i\Delta^{2n}. Pick up other Δ1\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. B3B_3 don’t have σiσj=σjσi\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Δmy=xΔm+1yx\Delta^m y = x\Delta^{m+1} y' if and only if the first 3 letter in the current presentation of yy is Δ\Delta.

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σ11)=Δ2σ12\begin{aligned} \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{aligned}

I wrote a Haskell implementation of the algorithm.
Posted by Chao Xu on .
Tags: braid group, BSU REU, computational complexity.