×

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
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

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: Jones and Bartlett Publishers Boston · Zbl 0764.20017
[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).; 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., (The Art of Computer Programming, Volume 3: Sorting and Searching (1998), Addison-Wesley, Reading: Addison-Wesley, Reading Massachusetts) · Zbl 0895.68054
[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, (The GAP Manual (1997)), (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. 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.