✦ LIBER ✦

On complexity of the word problem in braid groups and mapping class groups

✍ Scribed by Hessam Hamidi-Tehrani

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 350 KB
Volume: 105
Category: Article
ISSN: 0166-8641
DOI: 10.1016/s0166-8641(99)00063-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 g 2 ). 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.

📜 SIMILAR VOLUMES

A New Algorithm for Solving the Word Pro

A New Algorithm for Solving the Word Problem in Braid Groups

✍ D. Garber; S. Kaplan; M. Teicher 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 148 KB

One of the most interesting questions about a group is whether its word problem can be solved and how. The word problem in the braid group is of particular interest to topologists, algebraists, and geometers, and is the target of intensive current research. We look at the braid group from a topologi

The complexity of the word problem for a

The complexity of the word problem for abelian l-groups

✍ Volker Weispfenning 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 365 KB

A New Approach to the Word and Conjugacy

A New Approach to the Word and Conjugacy Problems in the Braid Groups

✍ Joan Birman; Ki Hyoung Ko; Sang Jin Lee 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 638 KB

A new presentation of the n-string braid group B n is studied. Using it, a new solution to the word problem in B n is obtained which retains most of the desirable features of the Garside Thurston solution, and at the same time makes possible certain computational improvements. We also give a related

The complexity of Dehn's algorithm for w

The complexity of Dehn's algorithm for word problems in groups

✍ B Domanski; M Anshel 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 361 KB

On Commutation Classes of Reduced Words

On Commutation Classes of Reduced Words in Weyl Groups

✍ Robert Bédard 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 483 KB

This paper is concerned with commutation classes of reduced words in Weyl groups. It is divided in three sections. In the first, we give a recursive formula for the number of reduced words in a commutation class. In the second, we give a tableau-like description of all the reduced words adapted to a

Torsion in the mapping class group and i

Torsion in the mapping class group and its cohomology

✍ H. Glover; G. Mislin 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 765 KB