A fast method for comparing braids

ABSTRACT. We describe a new method for comparing braid words which relies both on the automatic structure of the braid groups and on the existence of a linear ordering on braids. This syntactical algorithm is a direct generalization of the classical word reduction used in the description of free groups, and is more efficient in practice than all previously known methods. We consider in this paper the classical braid isotopy problem, i.e., the question of deciding if a given two-dimensional diagram made of a series of mutually crossing strands can be transformed into another one by moving strands but not allowing one to pass through another one. As is well-known, this problem became a question of algebra after E. Artin in the 20’s has rephrased it as the word problem for a family of effectively presented groups, Artin’s braid groups Bn. Many solutions have been described, beginning with Artin’s original construction that uses the geometric idea of combing the braids to obtain a normal form for braid words and a decomposition of the groups Bn as semidirect products of free groups ([1]). The starting point for modern braid comparison method is the purely algebraic result by Gar