# zbMATH — the first resource for mathematics

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.

##### 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)
Full Text:
##### References:
  Adjan, S.I., Defining relations and algorithmic problems for groups and semigroups, Proc. Steklov inst. math., 85, (1966)  Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading · Zbl 0207.01701  Artin, E., Theorie der zopfe, Hamburg abh., 4, 47-72, (1925) · JFM 51.0450.01  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  Clifford, A.H.; Preston, G.B., Algebraic theory of semi-groups, (1961), Am. Math. Soc.Survey 7 Providence · Zbl 0111.03403  Dehornoy, P., A fast method for computing braids, Adv. math., 125, 200-235, (1997) · Zbl 0882.20021  Elrifai, E.A.; Morton, H.R., Algorithms for positive braids, Quart. J. math. Oxford, 45, 479-497, (1994) · Zbl 0839.20051  Epstein, D.B.A., Word processing in groups, (1992), Jones and Bartlett Boston  Garside, F.A., The braid group and other groups, Quart. J. math. Oxford, 20, 235-254, (1969) · Zbl 0194.03303  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  Errera, A., Une problème d’énumération, Mém. acad. roy. belgique coll., 8, (1931) · JFM 57.1515.02  K. H. Ko, et al., Positive Presentation of the Braid Groups and the Embedding Problem  Paterson, M.S.; Rasborov, A.A., The set of minimal braids is co-NP-complete, J. algorithms., 12, 393-408, (1991) · Zbl 0726.68047  Remmers, J.H., On the geometry of semigroup presentations, Adv. math., 36, 283-296, (1980) · Zbl 0438.20041  Rudolph, L., Braided surfaces and Seifert ribbons for closed braids, Comm. math. helv., 58, 1-37, (1983) · Zbl 0522.57017  Sergiescu, V., Graphes planaires et présentations des groupes de tresses, Math. Z., 214, 477-490, (1993) · Zbl 0819.20040  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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.