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.<\/p>\n
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\u00e7alves 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.<\/p>","DOI":"10.1090\/mcom\/3392","type":"journal-article","created":{"date-parts":[[2018,7,25]],"date-time":"2018-07-25T09:28:35Z","timestamp":1532510915000},"page":"2027-2045","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial braid combing"],"prefix":"10.1090","volume":"88","author":[{"given":"Juan","family":"Gonz\u00e1lez-Meneses","sequence":"first","affiliation":[]},{"given":"Marithania","family":"Silvero","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2018,11,13]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.2307\/1969218","article-title":"Theory of braids","volume":"48","author":"Artin, E.","year":"1947","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"5","key":"2","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1080\/00927870802068664","article-title":"On residual properties of pure braid groups of closed surfaces","volume":"37","author":"Bardakov, Valerij G.","year":"2009","journal-title":"Comm. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0092-7872","issn-type":"print"},{"issue":"2","key":"3","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.jalgebra.2003.12.009","article-title":"On presentations of surface braid groups","volume":"274","author":"Bellingeri, Paolo","year":"2004","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"1409","DOI":"10.1016\/j.jalgebra.2007.10.023","article-title":"Lower central series of Artin-Tits and surface braid groups","volume":"319","author":"Bellingeri, Paolo","year":"2008","journal-title":"J. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0021-8693","issn-type":"print"},{"key":"5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1002\/cpa.3160220104","article-title":"On braid groups","volume":"22","author":"Birman, Joan S.","year":"1969","journal-title":"Comm. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"key":"6","series-title":"Annals of Mathematics Studies, No. 82","volume-title":"Braids, links, and mapping class groups","author":"Birman, Joan S.","year":"1974"},{"key":"7","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","volume":"315","author":"B\u00fcrgisser, Peter","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540605827"},{"key":"8","first-page":"243","article-title":"The braid groups of \ud835\udc38\u00b2 and \ud835\udc46\u00b2","volume":"29","author":"Fadell, Edward","year":"1962","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"9","doi-asserted-by":"crossref","unstructured":"L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter. Efficient algorithms for Lempel-Ziv encoding. Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT 1\u2013794), Lecture Notes in Comput. Sci. 1097, Springer-Verlag, Berlin 1996, 392-403.","DOI":"10.1007\/3-540-61422-2_148"},{"key":"10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.2307\/1994945","article-title":"The word problem and consequences for the braid groups and mapping class groups of the 2-sphere","volume":"131","author":"Gillette, Richard","year":"1968","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"issue":"2","key":"11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0022-4049(03)00163-4","article-title":"On the structure of surface pure braid groups","volume":"186","author":"Gon\u00e7alves, D. L.","year":"2004","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"key":"12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s10711-007-9207-z","article-title":"The braid groups of the projective plane and the Fadell-Neuwirth short exact sequence","volume":"130","author":"Gon\u00e7alves, Daciberg Lima","year":"2007","journal-title":"Geom. Dedicata","ISSN":"https:\/\/id.crossref.org\/issn\/0046-5755","issn-type":"print"},{"issue":"5","key":"13","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1016\/j.jpaa.2009.07.009","article-title":"Braid groups of non-orientable surfaces and the Fadell-Neuwirth short exact sequence","volume":"214","author":"Gon\u00e7alves, Daciberg Lima","year":"2010","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"issue":"3","key":"14","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1142\/S0218216501000949","article-title":"New presentations of surface braid groups","volume":"10","author":"Gonz\u00e1lez-Meneses, Juan","year":"2001","journal-title":"J. Knot Theory Ramifications","ISSN":"https:\/\/id.crossref.org\/issn\/0218-2165","issn-type":"print"},{"key":"15","isbn-type":"print","first-page":"23","article-title":"A survey of surface braid groups and the lower algebraic \ud835\udc3e-theory of their group rings","author":"Guaschi, John","year":"2015","ISBN":"https:\/\/id.crossref.org\/isbn\/9781571463012"},{"key":"16","isbn-type":"print","first-page":"193","article-title":"An invitation to Coxeter groups","author":"de la Harpe, Pierre","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/9810204426"},{"key":"17","isbn-type":"print","volume-title":"Algebraic topology","author":"Hatcher, Allen","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/052179160X"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/978-3-540-27836-8_76","article-title":"Word problems on compressed words","author":"Lohrey, Markus","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/3540228497"},{"key":"19","series-title":"Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Band 89","isbn-type":"print","volume-title":"Combinatorial group theory","author":"Lyndon, Roger C.","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/3540076425"},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","article-title":"Testing equivalence of morphisms on context-free languages","author":"Plandowski, Wojciech","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/354058434X"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"741","DOI":"10.4171\/CMH\/142","article-title":"Polynomial-time word problems","volume":"83","author":"Schleimer, Saul","year":"2008","journal-title":"Comment. Math. Helv.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-2571","issn-type":"print"},{"key":"22","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1017\/s0305004100076593","article-title":"Braid groups and the group of homeomorphisms of a surface","volume":"68","author":"Scott, G. P.","year":"1970","journal-title":"Proc. Cambridge Philos. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0008-1981","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-318\/S0025-5718-2018-03392-0\/mcom3392_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2019-88-318\/S0025-5718-2018-03392-0\/S0025-5718-2018-03392-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-318\/S0025-5718-2018-03392-0\/S0025-5718-2018-03392-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:10:12Z","timestamp":1776802212000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2019-88-318\/S0025-5718-2018-03392-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,13]]},"references-count":22,"journal-issue":{"issue":"318","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["S0025-5718-2018-03392-0"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3392","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2018,11,13]]}}}