The Art Gallery Guardian

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. \displaystyle \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 2011-07-05.
Tags: braid group, BSU REU, computational complexity.