Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

The Root Extraction Problem for Generic Braids

Abstract : We show that, generically, finding the k-th root of a braid is very fast. More precisely, we provide an algorithm which, given a braid x on n strands and canonical length l, and an integer k>1 , computes a k-th root of x, if it exists, or guarantees that such a root does not exist. The generic-case complexity of this algorithm is O(l(l+n)n3logn) . The non-generic cases are treated using a previously known algorithm by Sang-Jin Lee. This algorithm uses the fact that the ultra summit set of a braid is, generically, very small and symmetric (through conjugation by the Garside element Δ ), consisting of either a single orbit conjugated to itself by Δ or two orbits conjugated to each other by Δ .
Type de document :
Article dans une revue
Liste complète des métadonnées
Contributeur : Imb - Université de Bourgogne <>
Soumis le : lundi 6 janvier 2020 - 09:29:25
Dernière modification le : jeudi 16 avril 2020 - 14:30:06

Lien texte intégral




María Cumplido Cabello, Juan González-Meneses, Marithania Silvero. The Root Extraction Problem for Generic Braids. Symmetry, MDPI, 2019, 11 (11), pp.1327. ⟨10.3390/sym11111327⟩. ⟨hal-02428538⟩



Consultations de la notice