Polynomial braid combing

DOI10.1090/MCOM/3392MaRDI QIDQ4629388zbMATH OpenOpenAlexWikidataFDO

Authors Juan González-Meneses, Marithania Silvero

Publication date 22 March 2019

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

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

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Braid groups; Artin groups (20F36) Analysis of algorithms and problem complexity (68Q25)

Abstract: Braid combing is a procedure defined by Emil Artin to solve the word problem in braid groups for the first time. It is well-known to have exponential complexity. In this paper, we use the theory of straight line programs to give a polynomial algorithm which performs braid combing. This procedure can be applied to braids on surfaces, providing the first algorithm (to our knowledge) which solves the word problem for braid groups on surfaces with boundary in polynomial time and space. In the case of surfaces without boundary, braid combing needs to use a section from the fundamental group of the surface to the braid group. Such a section was shown to exist by Gonccalves and Guaschi, who also gave a geometric description. We propose an algebraically simpler section, which we describe explicitly in terms of generators of the braid group, and we show why the above procedure to comb braids in polynomial time does not work in this case.

Recommendations

• A new algorithm for solving the word problem in braid groups
• ALGORITHMS FOR POSITIVE BRAIDS
• scientific article; zbMATH DE number 1996520
• A new approach to the word and conjugacy problems in the braid groups
• Algorithmic recognition of quasipositive 4-braids of algebraic length three.

Cites work

• Automata, Languages and Programming
• Braid groups of non-orientable surfaces and the Fadell-Neuwirth short exact sequence
• Combinatorial group theory.
• Efficient algorithms for Lempel-Ziv encoding
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 849256 (Why is no real title available?)
• scientific article; zbMATH DE number 3323771 (Why is no real title available?)
• Lower central series of Artin-Tits and surface braid groups.
• New presentations of surface braid groups
• On braid groups
• On presentations of surface braid groups.
• On Residual Properties of Pure Braid Groups of Closed Surfaces
• On the structure of surface pure braid groups.
• Polynomial-time word problems.
• The braid groups of \(E^ 2\) and \(S^ 2\)
• The braid groups of the projective plane and the Fadell-Neuwirth short exact sequence.
• The Word Problem and Consequences for the Braid Groups and Mapping Class Groups of the 2-Sphere
• Theory of braids

Cited in

(2)

• A new algorithm for solving the word problem in braid groups
• Composition problems for braids

This page was built for publication: Polynomial braid combing

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