The length of elements in free solvable groups
HTML articles powered by AMS MathViewer
- by Carl Droms, Jacques Lewin and Herman Servatius PDF
- Proc. Amer. Math. Soc. 119 (1993), 27-33 Request permission
Abstract:
We examine the relationship between the complexity of the word problem for a presentation and the complexity of the problem of determining the length of a shortest word equivalent to a given word. Our main result is that the length of the element represented by a word in a free solvable group can be determined in polynomial time.References
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694
- Christos H. Papadimitriou, The Euclidean traveling salesman problem is $NP$-complete, Theoret. Comput. Sci. 4 (1977), no. 3, 237–244. MR 455550, DOI 10.1016/0304-3975(77)90012-3
- Walter Parry, Growth series of some wreath products, Trans. Amer. Math. Soc. 331 (1992), no. 2, 751–759. MR 1062874, DOI 10.1090/S0002-9947-1992-1062874-3
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 119 (1993), 27-33
- MSC: Primary 20F06; Secondary 20F14
- DOI: https://doi.org/10.1090/S0002-9939-1993-1160298-8
- MathSciNet review: 1160298