Solving the conjugacy problem in Garside groups by cyclic sliding.

DOI10.1016/J.JSC.2010.01.013zbMATH Open1235.20032DBLPjournals/jsc/GebhardtG10arXiv0809.0948OpenAlexW1512261170WikidataQ59275301 ScholiaQ59275301MaRDI QIDQ972844FDOQ972844

Volker Gebhardt, Juan González-Meneses

Publication date: 21 May 2010

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0809.0948

Recommendations

• The cyclic sliding operation in Garside groups.
• A new approach to the conjugacy problem in Garside groups.
• Subgroup conjugacy problem for Garside subgroups of Garside groups
• Conjugacy in Garside groups. I: Cyclings, powers and rigidity.
• Conjugacy problem for braid groups and Garside groups.

zbMATH Keywords

algorithmsconjugacy problemcyclingGarside groupscomplexity analysisnormal form theoremsconjugacy search problemultra summit setscyclic sliding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Braid groups; Artin groups (20F36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Conjugacy problem for braid groups and Garside groups.
• Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
• A new approach to the word and conjugacy problems in the braid groups
• Artin groups of finite type are biautomatic
• ALGORITHMS FOR POSITIVE BRAIDS
• Groupes de Garside
• Conjugacy in Garside groups. III: Periodic braids.
• Conjugacy in Garside groups. I: Cyclings, powers and rigidity.
• A new approach to the conjugacy problem in Garside groups.
• Abelian Subgroups of Garside Groups
• The cyclic sliding operation in Garside groups.

Cited In (18)

• The development version of the \texttt{CHEVIE} package of \texttt{GAP3}.
• Dual Garside structure and reducibility of braids.
• On the minimal positive standardizer of a parabolic subgroup of an Artin-Tits group
• Birth of Garside groups in memory of Patrick Dehornoy
• Basic results on braid groups.
• Limits of sequences of pseudo-Anosov maps and of hyperbolic 3-manifolds
• On the centralizer of generic braids
• Subgroup conjugacy problem for Garside subgroups of Garside groups
• The cyclic sliding operation in Garside groups.
• The root extraction problem in braid group-based cryptography
• Algorithms for Garside calculus
• A family of pseudo-Anosov braids with large conjugacy invariant sets.
• PreGarside monoids and groups, parabolicity, amalgamation, and FC property.
• THE CONJUGACY PROBLEM IN SMALL GAUSSIAN GROUPS
• A new approach to the conjugacy problem in Garside groups.
• How to read the length of a braid from its curve diagram.
• Reducible braids and Garside theory.
• Fast Nielsen-Thurston classification of braids.

This page was built for publication: Solving the conjugacy problem in Garside groups by cyclic sliding.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972844)