Efficient solutions to the braid isotopy problem.

DOI10.1016/J.DAM.2007.12.009zbMATH Open1197.20030arXivmath/0703666OpenAlexW2052485254MaRDI QIDQ1003697FDOQ1003697

Patrick Dehornoy

Publication date: 4 March 2009

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

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.

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)

Cites Work

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

Cited In (10)

• Geometric intersection of curves on punctured disks
• Dynnikov coordinates on punctured torus
• On the topological entropy of families of braids
• A general approach to fast prototype the topology of braided structures
• Curve diagrams, laminations, and the geometric complexity of braids
• Algorithms for Garside calculus
• Coherence via focusing for symmetric skew monoidal categories
• Uniform measures on braid monoids and dual braid monoids
• Topological Entropy of Surface Braids and Maximally Efficient Mixing
• Title not available (Why is that?)

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)