zbMATH — the first resource for mathematics

Solving the conjugacy problem in Garside groups by cyclic sliding. (English) Zbl 1235.20032
Summary: We present a solution to the conjugacy decision problem and the conjugacy search problem in Garside groups, which is theoretically simpler than the usual one, with no loss of efficiency. This is done by replacing the well-known cycling and decycling operations by a new one, called cyclic sliding, which appears to be a more natural choice.
We give an analysis of the complexity of our algorithm in terms of fundamental operations with simple elements, so our analysis is valid for every Garside group.
This paper intends to be self-contained, not requiring any previous knowledge of prior algorithms, and includes all the details for the algorithm to be implemented on a computer.

MSC:
 20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) 20F36 Braid groups; Artin groups 68W30 Symbolic computation and algebraic computation 68Q25 Analysis of algorithms and problem complexity
Full Text:
References:
 [1] Birman, J.S.; Gebhardt, V.; González-Meneses, J., Conjugacy in garside groups I: cycling, powers and rigidity, Groups geom. dyn., 1, 221-279, (2007) · Zbl 1160.20026 [2] Birman, J.S.; Gebhardt, V.; González-Meneses, J., Conjugacy in garside groups III: periodic braids, J. algebra, 316, 746-776, (2007) · Zbl 1165.20031 [3] Birman, J.S.; Ko, K.Y.; Lee, S.J., A new approach to the word and conjugacy problems in the braid groups, Adv. math., 139, 322-353, (1998) · Zbl 0937.20016 [4] Charney, R., Artin groups of finite type are biautomatic, Math. ann., 292, 671-683, (1992) · Zbl 0736.57001 [5] Dehornoy, P.; Paris, L., Gaussian groups and garside groups, two generalizations of Artin groups, Proc. lond. math. soc. (3), 79, 569-604, (1999) · Zbl 1030.20021 [6] Dehornoy, P., Groupes de garside, Ann. sci. ec. norm. super. (4), 35, 267-306, (2002) · Zbl 1017.20031 [7] ElRifai, E.; Morton, H., Algorithms for positive braids, Q. J. math. oxf. ser. (2), 45, 479-497, (1994) · Zbl 0839.20051 [8] Epstein, D.B.A.; Cannon, J.W.; Holt, D.F.; Levy, S.V.F.; Paterson, M.S.; Thurston, W.P., Word processing in groups, (1992), Jones and Bartlett Publishers Boston [9] Franco, N.; González-Meneses, J., Conjugacy problem for braid groups and garside groups, J. algebra, 266, 112-132, (2003) · Zbl 1043.20019 [10] Gebhardt, V., A new approach to the conjugacy problem in garside groups, J. algebra, 292, 282-302, (2005) · Zbl 1105.20032 [11] Gebhardt, V, González-Meneses, J., 2009. The cyclic sliding operation in Garside groups. Math. Z., in press (doi:10.1007/s00209-009-0502-2). [12] Knuth, D.E., () [13] Lee, E.-K.; Lee, S.J., Abelian subgroups of garside groups, Comm. algebra, 36, 1121-1139, (2008) · Zbl 1155.20037 [14] Michel, J., Garside and braid monoids and groups, (), (Chapter 82). Available at http://www.math.jussieu.fr/ jmichel/htm/CHAP082.htm
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.