A new approach to the word and conjugacy problems in the braid groups. (English) Zbl 0937.20016

The \(n\)-string braid group \(B_n\) has the presentation: \[ \langle\sigma_1,\dots,\sigma_{n-1};\;\sigma_i\sigma_j=\sigma_j\sigma_i\;(|i-j|>1),\;\sigma_i\sigma_j\sigma_i=\sigma_j\sigma_i\sigma_j\;(|i-j|=1)\rangle. \] This presentation is usually called the Artin presentation. The authors propose a new presentation as follows: \[ \begin{aligned}\langle a_{ts} (1\leq s < t\leq n);\;a_{ts} a_{rq}&=a_{rq}a_{ts} (t-r)(t-q)(s-r)(s-q)>0,\\ a_{ts}a_{sr}&=a_{tr}a_{ts}=a_{sr}a_{tr} (1\leq r<s<t\leq n)\rangle,\end{aligned} \] where \(a_{ts}\) are defined by \(a_{ts}=(\sigma_{t-1}\sigma_{t-2}\cdots\sigma_{s+1})\sigma_s(\sigma_{s+1}^{-1}\cdots\sigma^{-1}_{t-2}\sigma^{-1}_{t-1})\). The authors show that this presentation retains most of the desirable features of the Artin presentation, and at the same time makes certain computational improvements possible.
Using the new presentation, the authors give a polynomial time algorithm for the word problem and also an algorithm for the conjugacy problem in the braid groups.


20F36 Braid groups; Artin groups
20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
Full Text: DOI arXiv


[1] Adjan, S. I., Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov Inst. Math., 85 (1966) · Zbl 0204.01702
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The design and analysis of computer algorithms (1974), Addison-Wesley: Addison-Wesley Reading · Zbl 0207.01701
[3] Artin, E., Theorie der Zopfe, Hamburg Abh., 4, 47-72 (1925)
[4] Birman, J. S.; Menasco, W., Studying links via closed braids III: Classifying links which are closed 3-braids, Pacific J. Math., 161, 25-113 (1993) · Zbl 0813.57010
[5] Clifford, A. H.; Preston, G. B., Algebraic Theory of Semi-groups (1961), Am. Math. Soc.Survey 7: Am. Math. Soc.Survey 7 Providence · Zbl 0111.03403
[6] Dehornoy, P., A fast method for computing braids, Adv. Math., 125, 200-235 (1997) · Zbl 0882.20021
[7] Elrifai, E. A.; Morton, H. R., Algorithms for positive braids, Quart. J. Math. Oxford, 45, 479-497 (1994) · Zbl 0839.20051
[8] Epstein, D. B.A., Word Processing in Groups (1992), Jones and Bartlett: Jones and Bartlett Boston · Zbl 0764.20017
[9] Garside, F. A., The braid group and other groups, Quart. J. Math. Oxford, 20, 235-254 (1969) · Zbl 0194.03303
[10] Kang, E. S.; Ko, K. H.; Lee, S. J., Band-generator presentation for the 4-braid group, Topology Appl., 78, 39-60 (1997) · Zbl 0879.57005
[11] Errera, A., Une problème d’énumération, Mém. Acad. Roy. Belgique Coll., 8 (1931)
[12] K. H. Ko, et al.; K. H. Ko, et al.
[13] Paterson, M. S.; Rasborov, A. A., The set of minimal braids is co-NP-complete, J. Algorithms., 12, 393-408 (1991) · Zbl 0726.68047
[14] Remmers, J. H., On the geometry of semigroup presentations, Adv. Math., 36, 283-296 (1980) · Zbl 0438.20041
[15] Rudolph, L., Braided surfaces and Seifert ribbons for closed braids, Comm. Math. Helv., 58, 1-37 (1983) · Zbl 0522.57017
[16] Sergiescu, V., Graphes planaires et présentations des groupes de tresses, Math. Z., 214, 477-490 (1993) · Zbl 0819.20040
[17] Xu, P. J., The genus of closed 3-braids, J. Knot Theory Ramifications, 1, 303-326 (1992) · Zbl 0773.57007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.