A new approach to the word and conjugacy problems in the braid groups

DOI10.1006/aima.1998.1761zbMath0937.20016arXivmath/9712211OpenAlexW2156285104MaRDI QIDQ1273842

Joan S. Birman, Ki Hyoung Ko, Sang Jin Lee

Publication date: 29 May 2000

Published in: Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

presentations Artin presentations braid groups polynomial time algorithms word problems conjugacy problems

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Braid groups; Artin groups (20F36) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

On the singular braid monoid ⋮ Almost all strongly quasipositive braid closures are fibered ⋮ Garside and Quadratic Normalisation: A Survey ⋮ INDECOMPOSABLE SURFACE BUNDLES OVER SURFACES ⋮ A TEMPERLEY-LIEB BASIS COMING FROM THE BRAID GROUP ⋮ TOWARDS AN IMPLEMENTATION OF THE B–H ALGORITHM FOR RECOGNIZING THE UNKNOT ⋮ Positivities of Knots and Links and the Defect of Bennequin Inequality ⋮ The cohomology class of the mod 4 braid group ⋮ Garside groups and geometry: Some thoughts for Patrick Dehornoy ⋮ Interval groups related to finite Coxeter groups. I ⋮ Acylindricity of the action of right-angled Artin groups on extension graphs ⋮ Bijective combinatorics of positive braids ⋮ Braided open book decompositions in \(S^{3}\) ⋮ Smallest noncyclic quotients of braid and mapping class groups ⋮ Sublinks of strongly quasipositive links ⋮ Representations of flat virtual braids which do not preserve the forbidden relations ⋮ Abelian Subgroups of Garside Groups ⋮ The seven-strand braid group is \(\mathrm{CAT}(0)\) ⋮ 3-braid knots with maximal 4-genus ⋮ A new Garside structure on torus knot groups and some complex braid groups ⋮ TORIC REFLECTION GROUPS ⋮ Petal grid diagrams of torus knots ⋮ A class of Garside groupoid structures on the pure braid group ⋮ Braid Groups and Euclidean Simplices ⋮ Automorphism group of the commutator subgroup of the braid group ⋮ Cryptanalysis of the shifted conjugacy authentication protocol ⋮ ON THE IMAGE OF THE LAWRENCE–KRAMMER REPRESENTATION ⋮ THE WELL-ORDERING OF DUAL BRAID MONOID ⋮ On the structure of the centralizer of a braid ⋮ Gröbner–Shirshov bases and their calculation ⋮ Gröbner-Shirshov Bases for Braid Groups in Adyan-Thurston Generators ⋮ On McMullen's and other inequalities for the Thurston norm of link complements ⋮ BRAID MONODROMY OF SOME BRIESKORN–PHAM SINGULARITIES ⋮ A partial order on the symmetric group and new \(K(\pi,1)\)'s for the braid groups ⋮ Non-crossing partition lattices in finite real reflection groups ⋮ Hopf plumbing, arborescent Seifert surfaces, baskets, espaliers, and homogeneous braids ⋮ The infimum, supremum, and geodesic length of a braid conjugacy class. ⋮ FINITE THURSTON-TYPE ORDERINGS ON DUAL BRAID MONOIDS ⋮ A NOTE ON CLOSED 3-BRAIDS ⋮ The center of thin Gaussian groups ⋮ GEOMETRIC PRESENTATIONS FOR THE PURE BRAID GROUP ⋮ Laver's results and low-dimensional topology ⋮ Random quotients of the modular group are rigid and essentially incompressible ⋮ Cross-sections of unknotted ribbon disks and algebraic curves ⋮ Normal forms in braid groups with respect to some Gröbner–Shirshov basis ⋮ GRÖBNER–SHIRSHOV BASES FOR FREE INVERSE SEMIGROUPS ⋮ Garside Structure for Singular Braid Monoid in Birman, Ko, Lee Generators ⋮ The defect of Bennequin-Eliashberg inequality and Bennequin surfaces ⋮ Automatic Structures for Torus Link Groups ⋮ Generalized noncrossing partitions and combinatorics of Coxeter groups ⋮ Conjugacy Problem for Subgroups with Applications to Artin Groups and Braid Type Group ⋮ GROWTH SERIES FOR ARTIN GROUPS OF DIHEDRAL TYPE ⋮ A Garside-theoretic analysis of the Burau representations ⋮ Decomposition of Garside groups and self-similar \(L\)-algebras ⋮ The dual braid monoid ⋮ On the centralizer of generic braids ⋮ Noncrossing partitions for periodic braids ⋮ The \(n\)th root of a braid is unique up to conjugacy. ⋮ A class of hash functions based on the Algebraic Eraser\(^{\text{TM}}\) ⋮ Computation of centralizers in braid groups and Garside groups. ⋮ Counting chains in the noncrossing partition lattice via the \(W\)-Laplacian ⋮ Structure groups of \(L\)-algebras and Hurwitz action ⋮ A dual braid monoid for the free group. ⋮ Experiments on growth series of braid groups ⋮ On some torus knot groups and submonoids of the braid groups ⋮ Cyclic amalgams, HNN extensions, and Garside one-relator groups ⋮ Fundamental group of discriminant complements of Brieskorn-Pham polynomials ⋮ Garside groups are strongly translation discrete. ⋮ The conjugacy problem and virtually cyclic subgroups in the Artin braid group quotient \(B_n/[P_{n},P_{n}\)] ⋮ Combinatorics of normal sequences of braids ⋮ Boundary braids ⋮ Garside theory and subsurfaces: some examples in braid groups ⋮ Acylindrical hyperbolicity and Artin-Tits groups of spherical type ⋮ Homology of Gaussian groups. ⋮ Criterion of Hurwitz equivalence for quasipositive factorizations of 3-braids. ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ Dual garside structures and Coxeter sortable elements ⋮ Conjugacy problem for braid groups and Garside groups. ⋮ Noncrossing partitions and Bruhat order ⋮ A simple algorithm for finding short sigma-definite representatives. ⋮ Quasipositive links and connected sums ⋮ On some quadratic algebras. I \(\frac{1}{2}\): Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials ⋮ Braid ordering and the geometry of closed braid ⋮ Affine braid groups: a better platform than braid groups for cryptology? ⋮ Complete positive group presentations. ⋮ Periodic elements in Garside groups. ⋮ The rotating normal form of braids is regular ⋮ Infinitesimal quotients of the braid group. ⋮ Finite orbits of Hurwitz actions on braid systems. ⋮ Every braid admits a short sigma-definite expression. ⋮ Small braids with large ultra summit set. ⋮ Twisted conjugacy in braid groups. ⋮ Fast Nielsen-Thurston classification of braids. ⋮ Asymptotic combinatorics of Artin-Tits monoids and of some other monoids ⋮ Algorithmic recognition of quasipositive braids of algebraic length two. ⋮ A well-ordering of dual braid monoids. ⋮ Gröbner-Shirshov bases for some braid groups. ⋮ On the Hurwitz action on quasipositive factorizations of 3-braids. ⋮ Gröbner-Shirshov bases, conformal algebras, and pseudo-algebras. ⋮ Alternating normal forms for braids and locally Garside monoids. ⋮ Conjugacy in Garside groups. III: Periodic braids. ⋮ Uniform measures on braid monoids and dual braid monoids ⋮ Parabolic subgroups of Garside groups. ⋮ A Garside-theoretic approach to the reducibility problem in braid groups. ⋮ Dual braid monoids, Mikado braids and positivity in Hecke algebras ⋮ On presentations of generalizations of braids with few generators. ⋮ Conjugacy in Garside groups. I: Cyclings, powers and rigidity. ⋮ Conjugacy in Garside groups. II: Structure of the ultra summit set. ⋮ THE CONJUGACY PROBLEM IN SMALL GAUSSIAN GROUPS ⋮ Zero loci of skew-growth functions for dual Artin monoids ⋮ The braided Ptolemy-Thompson group is finitely presented. ⋮ Hurwitz orbits of primitive factorizations of a Coxeter element. ⋮ The cyclic sliding operation in Garside groups. ⋮ Basic results on braid groups. ⋮ Reading the dual Garside length of braids from homological and quantum representations. ⋮ Solving the conjugacy problem in Garside groups by cyclic sliding. ⋮ Non-crossing partitions of type \((e,e,r)\). ⋮ The group of fractions of a torsion free lcm monoid is torsion free. ⋮ The language of geodesics for Garside groups ⋮ On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids ⋮ Dual Garside structure and reducibility of braids. ⋮ Reflection Groups ⋮ Braids, their Properties and Generalizations ⋮ Conjugacy Classes of the 3-Braid Group ⋮ Classifying spaces from Ore categories with Garside families ⋮ Translation numbers in a Garside group are rational with uniformly bounded denominators. ⋮ Attack on Kayawood protocol: uncloaking private keys ⋮ On the cycling operation in braid groups. ⋮ Braid group action on projective quantum \(\mathfrak{sl}(2)\) modules ⋮ 3-braid knots do not admit purely cosmetic surgeries ⋮ Schur rings over infinite groups. II ⋮ Coxeter-Catalan combinatorics and Temperley-Lieb algebras ⋮ Gröbner-Shirshov basis for the braid group in the Birman-Ko-Lee generators. ⋮ Helly meets Garside and Artin ⋮ A symmetrical presentation for the singular part of the symmetric inverse monoid. ⋮ On finite Thurston-type orderings of braid groups ⋮ Subgroup conjugacy problem for Garside subgroups of Garside groups ⋮ Noncommutative independence from the braid group \({\mathbb{B}_{\infty}}\) ⋮ A new algorithm for recognizing the unknot ⋮ Garside combinatorics for Thompson's monoid \(F^+\) and a hybrid with the braid monoid \(B_{\infty }^{+}\) ⋮ Left-Garside categories, self-distributivity, and braids ⋮ Non-crossing partitions ⋮ An attack on the Walnut digital signature algorithm ⋮ UNKNOTTING NUMBER AND GENUS OF 3-BRAID KNOTS ⋮ On definite strongly quasipositive links and L-space branched covers ⋮ Three-dimensional FC Artin groups are CAT(0). ⋮ A new approach to the conjugacy problem in Garside groups. ⋮ ON THE DEFINITION OF GRAPH INDEX ⋮ Lawrence-Krammer-Bigelow representations and dual Garside length of braids. ⋮ Finite complex reflection arrangements are \(K(\pi,1)\) ⋮ A new algorithm for solving the word problem in braid groups ⋮ Identifying half-twists using randomized algorithm methods. ⋮ Explicit presentations for the dual braid monoids

Cites Work