The Library
The linearity of the conjugacy problem in word-hyperbolic groups
Tools
UNSPECIFIED (2006) The linearity of the conjugacy problem in word-hyperbolic groups. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 16 (2). pp. 287-305. ISSN 0218-1967.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The main result proved in this paper is that the conjugacy problem in word-hyperbolic groups is solvable in linear time. This is using a standard RAM model of computation, in which basic arithmetical operations on integers are assumed to take place in constant time. The constants involved in the linear time solution are all computable explicitly.
We also give a proof of the result of Mike Shapiro that in a word-hyperbolic group a word in the generators can be transformed into short-lex normal form in linear time. This is used in the proof of our main theorem, but is a significant theoretical result of independent interest, which deserves to be in the literature. Previously the best known result was a quadratic estimate.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Journal or Publication Title: | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION | ||||
Publisher: | WORLD SCIENTIFIC PUBL CO PTE LTD | ||||
ISSN: | 0218-1967 | ||||
Official Date: | April 2006 | ||||
Dates: |
|
||||
Volume: | 16 | ||||
Number: | 2 | ||||
Number of Pages: | 19 | ||||
Page Range: | pp. 287-305 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |