Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Polynomial braid combing

Authors: Juan González-Meneses and Marithania Silvero
Journal: Math. Comp. 88 (2019), 2027-2045
MSC (2010): Primary 20F36, 20F10; Secondary 68Q25
Published electronically: November 13, 2018
MathSciNet review: 3925496
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Braid combing is a procedure defined by Emil Artin to solve the word problem in braid groups. 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 Gonçalves 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 20F36, 20F10, 68Q25

Retrieve articles in all journals with MSC (2010): 20F36, 20F10, 68Q25

Additional Information

Juan González-Meneses
Affiliation: Departamento de Álgebra, Facultad de Matemáticas, Instituto de Matemáticas (IMUS), Universidad de Sevilla, Av. Reina Mercedes s/n, 41012 Sevilla, Spain

Marithania Silvero
Affiliation: Institute of Mathematics, Polish Academy of Sciences, ul. Śniadeckich, 8, 00-656 Warsaw, Poland

Received by editor(s): January 3, 2018
Received by editor(s) in revised form: June 15, 2018
Published electronically: November 13, 2018
Additional Notes: Both authors were partially supported by the Spanish research projects MTM2013-44233-P, MTM2016-76453-C2-1-P and FEDER
Article copyright: © Copyright 2018 American Mathematical Society