zbMATH — the first resource for mathematics

Algorithms for positive braids. (English) Zbl 0839.20051
The elements of the braid group $$B_n= \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$$ which can be written as a word in positive powers of the generators $$\sigma_1, \dots, \sigma_{n-1}$$ are called positive braids. For braids $$A$$, $$B$$ write $$A\leq B$$ when $$B= C_1 AC_2$$ for some positive braids $$C_1$$, $$C_2$$. The authors call a positive braid $$F$$ a positive permutation braid if $$F\leq \Delta_n$$, where $$\Delta_n= \sigma_1 \dots \sigma_{n-1} \sigma_1\dots \sigma_{n-2} \dots \sigma_1 \sigma_2 \sigma_1$$. The authors study the properties of positive permutation braids. Particularly, they give two canonical forms for positive braids as products of positive permutation braids. This result enables the authors to simplify Garside’s solution of the word and conjugacy problems in $$B_n$$. The authors also give algorithms deciding (given a positive braid $$F$$ and integer $$k$$): 1) whether $$\Delta^k_n\leq F$$; 2) whether $$F\leq \Delta^k_n$$. It should be noted that similar results about positive permutation braids were obtained and the same canonical form was given in the papers of G. S. Makanin [Mat. Sb., Nov. Ser 86 (128), 171-179 (1971; Zbl 0229.20035)] and V. B. Styshnev [Izv. Akad. Nauk SSSR, Ser. Mat. 42, 1120-1131 (1978; Zbl 0402.20029)].

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