Abstract
A method for constructing algorithms solving the word and comparison problems for mapping class groups (in particular, for the braid group) is presented, and a family of one-side invariant orderings on the mapping class group of a surface with boundary is described. A method for constructing comparison algorithms for all finite orderings on the mapping class group of any surface with boundary is described, a fast and simple comparison algorithm for the Dehornoy order on the braid group is presented, examples of normal forms for braid groups are given, and algorithms for finding the forms are indicated. Bibliography: 15 titles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts (1979).
J. S. Birman, Braids, Links, and Mapping Class Groups (Ann. Math. Stud., 82), Princeton Univ. Press, Princeton, New Jersey (1974).
J. S. Birman, K. H. Ko, and S. J. Lee, “A new approach to the word and conjugacy problem in the braid groups,” Adv. Math., 139, 322–353 (1998).
P. Dehornoy, “A fast method of comparing braids,” Adv. Math., 125, 200–235 (1997).
D. Epstein et al., Word Processing in Groups, Jones and Bartlett Publs. (1992).
R. Fenn, M. T. Greene, D. Rolfsen, C. Rourke, and B. Wiest, “Ordering the braid groups,” Pacific J. Math., 191, 41–74 (1999).
H. Hamidi-Tehrani, “On complexity of the word problem in braid groups and mapping class groups,” preprint (1998).
L. Mosher, “Classification of pseudo-Anosovs,” in: Low Dimensional Topology and Kleinian Groups (1986), pp. 13–75.
L. Mosher, “Mapping class groups are automatic,” Ann. Math., 142, 303–384 (1995).
L. Mosher, “A user's guide to the mapping class group: Once punctured surfaces,” in: Geometric and Computational Perspectives on Infinite Groups (DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25), (1996), pp. 101–174.
C. Rourke and B. Wiest, “Order automatic mapping class groups,” Pacific J. Math., 194, 209–227 (2000).
H. Short and B. Wiest, “Orderings of mapping class groups after Thurston,” preprint http://www.pims.math.ca/~ bertw/ (2000).
S. Kaplan and M. Teicher, “Solving the braid word problem via the fundamental group,” preprint (2001).
D. Garber, S. Kaplan, and M. Teicher, “A new algorithm for solving the word problem in braid groups,” preprint (2001).
A. M. Vershik, “Dynamical theory of growth in groups: entropy, boundary, examples,” Usp. Mat. Nauk, 55,No. 4, 59–129 (2000).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Malyutin, A.V. Fast Algorithms for Identification and Comparison of Braids. Journal of Mathematical Sciences 119, 101–111 (2004). https://doi.org/10.1023/B:JOTH.0000008747.72654.14
Issue Date:
DOI: https://doi.org/10.1023/B:JOTH.0000008747.72654.14