The Art Gallery Guardian

Linear time algorithm for the word problem on


The word problem is solved if one can put in Garside normal form. The process is trivial in and can be done in linear time on a Turing machine. Remember .

  1. Rewrite all generator with negative exponents into ones with positive exponents and a .
  2. Move every to the beginning of the word. First locate the last , and move it forward using the relations and . Pick up other ’s in between.
  3. 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 . don’t have relation, therefore if a new is created from moving ’s around, it is a local event. To be precise, during this process, if and only if the first 3 letter in the current presentation of is .

A demonstration on a positive word.

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