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

Birman, Joan; Ko, Ki Hyoung; Lee, Sang Jin

Adv. Math. 139, No. 2, 322-353 (1998).

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.

Reviewer: A.M.Akimenkov (Krasnogorsk)

MSC:

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)

Keywords:

braid groups; presentations; Artin presentations; polynomial time algorithms; word problems; conjugacy problems

References:

[1]	Adjan, S. I., Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov Inst. Math., 85 (1966)
[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) · JFM 51.0450.01
[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) · JFM 57.1515.02
[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