Solving the conjugacy problem in Garside groups by cyclic sliding.

DOI10.1016/J.JSC.2010.01.013MaRDI QIDQ972844zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Volker Gebhardt, Juan González-Meneses

Publication date 21 May 2010

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

Full work available at URL https://arxiv.org/abs/0809.0948, https://idus.us.es/xmlui/handle/11441/42311

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)

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.

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.

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• A new approach to the conjugacy problem in Garside groups.
• A new approach to the word and conjugacy problems in the braid groups
• ALGORITHMS FOR POSITIVE BRAIDS
• Abelian Subgroups of Garside Groups
• Artin groups of finite type are biautomatic
• Conjugacy in Garside groups. I: Cyclings, powers and rigidity.
• Conjugacy in Garside groups. III: Periodic braids.
• Conjugacy problem for braid groups and Garside groups.
• Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
• Groupes de Garside
• The cyclic sliding operation in Garside groups.

Cited in

(21)

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

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)