Efficient solutions to the braid isotopy problem.

DOI10.1016/J.DAM.2007.12.009MaRDI QIDQ1003697zbMATH OpenOpenAlexFDO

Authors Patrick Dehornoy

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

braid groupsword problemnormal form theoremsgreedy normal formDynnikov coordinateshandle reductionsisotopy problemsubword reversings

Mathematics Subject Classification ID

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

Abstract: We describe the most efficient solutions to the word problem of Artin's braid group known so far, i.e., in other words, the most efficient solutions to the braid isotopy problem, including the Dynnikov method, which could be especially suitable for cryptographical applications. Most results appear in literature; however, some results about the greedy normal form and the symmetric normal form and their connection with grid diagrams may have never been stated explicitly.

Recommendations

• A new algorithm for solving the word problem in braid groups
• CONJUGACY IN ARTIN GROUPS AND APPLICATION TO THE CLASSIFICATION OF SURFACES
• Braid Group Cryptography
• scientific article; zbMATH DE number 2144676
• scientific article; zbMATH DE number 1759777

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1946843 (Why is no real title available?)
• scientific article; zbMATH DE number 1759777 (Why is no real title available?)
• scientific article; zbMATH DE number 2144676 (Why is no real title available?)
• A class of Garside groupoid structures on the pure braid group
• A fast method for comparing braids
• ALGORITHMS FOR POSITIVE BRAIDS
• Alternating normal forms for braids and locally Garside monoids.
• An algebraic method for public-key cryptography
• Artin groups of finite type are biautomatic
• Braids, Links, and Mapping Class Groups. (AM-82)
• Complete positive group presentations.
• Fragments of the word \(\Delta\) in a braid group
• Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups
• Groupes de Garside
• Groups with a complemented presentation
• Mapping class groups are automatic
• THE BRAID GROUP AND OTHER GROUPS
• The set of minimal braids is co-NP-complete
• The wellordering on positive braids
• Theory of braids

Cited in

(10)

• Geometric intersection of curves on punctured disks
• On the topological entropy of families of braids
• Dynnikov coordinates on punctured torus
• Topological entropy of surface braids and maximally efficient mixing
• A general approach to fast prototype the topology of braided structures
• The word problem for braided monoidal categories is unknot-hard
• Algorithms for Garside calculus
• Curve diagrams, laminations, and the geometric complexity of braids
• Coherence via focusing for symmetric skew monoidal categories
• Uniform measures on braid monoids and dual braid monoids

This page was built for publication: Efficient solutions to the braid isotopy problem.

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