1998/09/27 by Hessam Hamidi-Tehrani, Hamidi-Tehrani, Hessam · 1 citation
Computer Science · Mathematics · #20F10 #57S05 #68Q25 #Advanced Combinatorial Mathematics #Algebraic Geometry and Number Theory #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric Topology (math.GT) #Geometric and Algebraic Topology #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/9809154
openalex publication_date 1998/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that the word problem in the mapping class group of the once-punctured surface of genus g has complexity O(|w|2 g for |w| > log(g) where |w| is the length of the word in a (standard) set of generators. The corresponding bound in the case of the closed surface is O(|w|2 g2). We also carry out the same methods for the braid groups, and show that this gives a bound which improves the best known bound in this case; namely, the complexity of the word problem in the n-braid group is O(|w|2 n), for |w| > log n. We state a similar result for mapping class groups of surfaces with several punctures.