The Linearity of the Conjugacy Problem in Word-hyperbolic Groups
The Linearity of the Conjugacy Problem in Word-hyperbolic Groups
复制标题
词双曲群中共轭问题的线性
DOI：
10.1142/s0218196706002986
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
D. Holt
中科院分区：
文献类型：
--
作者：
D. Epstein;D. Holt
本文证明了字双曲群的共轭问题在线性时间内是可解的。这是使用一个标准的RAM计算模型，在这个模型中，对整数的基本算术运算被假设在恒定的时间内发生。线性时间解中的常数都是可显式计算的。我们还证明了MikeShapiro关于词双曲群中生成元中的一个词可以在线性时间内变换成短lex正规形的结果。这是用于证明我们的主要定理，但它是一个重要的理论结果的独立利益，值得在文献中。以前最著名的结果是二次估计。
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.